Submission #1691761
Source Code Expand
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <sstream>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
template <class T> inline void smin(T &a, T const &b) { a = min(a, b); }
template <class T> inline void smax(T &a, T const &b) { a = max(a, b); }
#ifdef LOCAL
#define dump(...) \
do { \
std::ostringstream os; \
os << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; \
print_to(os, ", ", "\n", __VA_ARGS__); \
std::cerr << os.str(); \
} while (0)
#define dump_(a) \
do { \
std::ostringstream os; \
os << __LINE__ << ":\t" << #a << " = ["; \
print_to_(os, ", ", "]\n", all(a)); \
std::cerr << os.str(); \
} while (0)
#else
#define dump(...)
#define dump_(...)
#endif
template <typename T>
void print_to(std::ostream &os, const char *, const char *tail, const T &fst) {
os << fst << tail;
}
template <typename Fst, typename... Rst>
void print_to(std::ostream &os, const char *del, const char *tail, const Fst &fst, const Rst &... rst) {
os << fst << del;
print_to(os, del, tail, rst...);
}
template <typename Iter>
void print_to_(std::ostream &os, const char *del, const char *tail, Iter bgn, Iter end) {
for (Iter it = bgn; it != end;) {
os << *it;
if (++it != end) {
os << del;
} else {
os << tail;
}
}
}
template <typename Fst, typename... Rst>
void println(const Fst &fst, const Rst &... rst) {
print_to(std::cout, "\n", "\n", fst, rst...);
}
template <typename Fst, typename... Rst>
void print(const Fst &fst, const Rst &... rst) {
print_to(std::cout, " ", "\n", fst, rst...);
}
template <typename Iter>
void println_(Iter bgn, Iter end) {
print_to_(std::cout, "\n", "\n", bgn, end);
}
template <typename Iter>
void print_(Iter bgn, Iter end) {
print_to_(std::cout, " ", "\n", bgn, end);
}
// const int MOD = 1000000007;
namespace trush {
int _ = (std::cout.precision(10), std::cout.setf(std::ios::fixed), std::cin.tie(0),
std::ios::sync_with_stdio(0), 0);
}
int N, K;
int A[101010];
bool match[101010];
string S[101010];
int s1_cnt = 0, s2_cnt = 0;
string S1[101010]; //マッチすべきもの
string S2[101010]; //マッチしないもの
int match_len(string s1, string s2)
{
int res = 0;
REP(i,min(s1.length(), s2.length())) {
if (s1[i] == s2[i]) res++;
else break;
}
return res;
}
signed main()
{
cin >> N >> K;
REP(i,K) {
cin >> A[i];
A[i]--;
match[A[i]] = true;
}
REP(i,N) {
if (match[i]) cin >> S1[s1_cnt++];
else cin >> S2[s2_cnt++];
}
//dump(s1_cnt, s2_cnt);
int m = INF, M = -INF;
for (int i=1; i<s1_cnt; i++) {
m = min(m, match_len(S1[0], S1[i]));
}
REP(i,s2_cnt) {
M = max(M, match_len(S1[0], S2[i]));
}
//dump(M, m);
if (M == -INF) {
cout << endl;
return 0;
}
if (M < m) {
//cout << M + 1 << endl;
cout << S1[0].substr(0, M + 1) << endl;
} else {
cout << -1 << endl;
}
}
Submission Info
Submission Time |
|
Task |
C - 検索 |
User |
hiyokko2 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
3971 Byte |
Status |
AC |
Exec Time |
62 ms |
Memory |
8192 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, long.txt, long2.txt, sample1.txt, sample2.txt, sample3.txt, long.txt, long2.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
4 ms |
2816 KB |
in10.txt |
AC |
4 ms |
2688 KB |
in11.txt |
AC |
7 ms |
3200 KB |
in12.txt |
AC |
3 ms |
2688 KB |
in13.txt |
AC |
6 ms |
2944 KB |
in14.txt |
AC |
3 ms |
2816 KB |
in15.txt |
AC |
3 ms |
2816 KB |
in16.txt |
AC |
3 ms |
2688 KB |
in17.txt |
AC |
3 ms |
2816 KB |
in18.txt |
AC |
3 ms |
2816 KB |
in19.txt |
AC |
6 ms |
3072 KB |
in2.txt |
AC |
7 ms |
3200 KB |
in20.txt |
AC |
6 ms |
2944 KB |
in3.txt |
AC |
32 ms |
7552 KB |
in4.txt |
AC |
40 ms |
8192 KB |
in5.txt |
AC |
3 ms |
2816 KB |
in6.txt |
AC |
3 ms |
2688 KB |
in7.txt |
AC |
3 ms |
2816 KB |
in8.txt |
AC |
6 ms |
3200 KB |
in9.txt |
AC |
39 ms |
8192 KB |
long.txt |
AC |
3 ms |
2944 KB |
long2.txt |
AC |
62 ms |
4352 KB |
sample1.txt |
AC |
3 ms |
2688 KB |
sample2.txt |
AC |
3 ms |
2688 KB |
sample3.txt |
AC |
3 ms |
2688 KB |