Submission #1836465


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int p = 100010;
vector<string> g[100010];

int main(void) {
  int n, k;
  cin >> n >> k;

  vector<int> a(k);
  for (int i = 0; i < k; i++) {
    cin >> a[i];
    a[i]--;
  }
  sort(a.begin(), a.end());

  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }

  for (int i = 0; i < n; i++) {
    string t = "";
    for (int j = 0; j < s[i].size(); j++) {
      g[i].push_back(t);
      t += s[i][j];
    }
    g[i].push_back(s[i]);
    if (*lower_bound(a.begin(), a.end(), i) != i) continue;
    p = min(p, (int)s[i].size());
  }

  string ans = "-1";
  for (int i = 0; i <= p; i++) {
    string t = s[a[0]].substr(0, i);
    bool can = true;
    for (int j = 0; j < n; j++) {
      if (j == a[0]) continue;
      if (*lower_bound(a.begin(), a.end(), j) == j) {
        can &= (g[j][i] == t);
      } else if (s[j].size() >= i) {
        can &= (g[j][i] != t);
      }
    }
    if (!can) continue;
    ans = t;
    break;
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Submission Time
Task C - 検索
User legosuke
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1086 Byte
Status TLE
Exec Time 2192 ms
Memory 1986424 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 22
TLE × 2
MLE × 6
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 43 ms 52352 KB
in10.txt AC 35 ms 51328 KB
in11.txt AC 28 ms 21248 KB
in12.txt AC 61 ms 87168 KB
in13.txt MLE 913 ms 1986424 KB
in14.txt AC 22 ms 17920 KB
in15.txt MLE 510 ms 1091068 KB
in16.txt AC 2 ms 2560 KB
in17.txt AC 40 ms 48128 KB
in18.txt AC 19 ms 12288 KB
in19.txt AC 25 ms 8320 KB
in2.txt AC 28 ms 12544 KB
in20.txt MLE 1077 ms -1780872 KB
in3.txt AC 65 ms 15872 KB
in4.txt AC 95 ms 16256 KB
in5.txt AC 69 ms 97408 KB
in6.txt AC 8 ms 7424 KB
in7.txt MLE 247 ms 487168 KB
in8.txt AC 26 ms 20480 KB
in9.txt AC 99 ms 16256 KB
long.txt MLE 1326 ms -1551624 KB
long2.txt TLE 2192 ms 1199480 KB
sample1.txt AC 2 ms 2560 KB
sample2.txt AC 2 ms 2560 KB
sample3.txt AC 3 ms 2560 KB