oj.uz

Submission #222704

# Submission time Handle Problem Language Result Execution time Memory
222704 2020-04-13T20:02:58 Z Bruteforceman Three Friends (BOI14_friends) C++11
100 / 100
 110 ms 55196 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
string s;
const int mod = 100000000 + 7;
const int base = 131;
long long power[2000005];

int main() {
  ios_base :: sync_with_stdio (false);
  cin.tie(0);
  int n;
  cin >> n >> s;
  n = s.size();
  int sz = (n - 1) / 2;
  power[0] = 1;
  for(int i = 1; i <= n; i++) {
    power[i] = (power[i - 1] * base) % mod;
  }
  auto func = [&] (int i, int j) {
    long long pw = 1;
    long long ans = 0;
    for(int x = i; x <= j; x++) {
      ans += pw * s[x];
      pw = (pw * base) % mod;
      ans %= mod;
    }
    return ans;
  };
  auto twice = [&] (int x) {
    return (x * (power[sz] + 1)) % mod;
  };
  
  int p = func(0, sz - 1);
  int q = func(sz + 1, n - 1);
  p = twice(p); q = twice(q);
   
  vector <long long> pre (n), suf (n);
  long long var = 0;
  for(int i = 0; i < n; i++) {
    pre[i] = var;
    var += power[i] * s[i];
    var %= mod;
  }
  var = 0;
  for(int i = n - 1; i >= 0; i--) {
    suf[i] = var;
    if(i == 0) break;
    var += power[i - 1] * s[i];
    var %= mod;
  } 
  set <int> can;
  int idx = -1;
  for(int i = 0; i < n; i++) {
    long long h = (pre[i] + suf[i]) % mod;
    if(h == p || h == q) {
      idx = i;
      can.insert(h);
      if(can.size() > 1) break;
    }
  }
  if(can.empty()) {
    cout << "NOT POSSIBLE" << endl;
  } else if (can.size() > 1) {
    cout << "NOT UNIQUE" << endl;
  } else {
    string aux;
    for(int i = 0; i < n; i++) {
      if(idx != i) aux += s[i];
    }
    cout << aux.substr(0, sz) << endl;
  }
  return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 5 ms 384 KB Output is correct
38 Correct 5 ms 384 KB Output is correct
39 Correct 5 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 5 ms 384 KB Output is correct
42 Correct 5 ms 384 KB Output is correct
43 Correct 5 ms 384 KB Output is correct
44 Correct 5 ms 384 KB Output is correct
45 Correct 5 ms 384 KB Output is correct
46 Correct 5 ms 384 KB Output is correct
47 Correct 5 ms 384 KB Output is correct
48 Correct 5 ms 384 KB Output is correct
49 Correct 5 ms 384 KB Output is correct
50 Correct 5 ms 384 KB Output is correct
51 Correct 5 ms 384 KB Output is correct
52 Correct 5 ms 384 KB Output is correct
53 Correct 5 ms 384 KB Output is correct
54 Correct 5 ms 384 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 53276 KB Output is correct
2 Correct 98 ms 55192 KB Output is correct
3 Correct 99 ms 55192 KB Output is correct
4 Correct 98 ms 55192 KB Output is correct
5 Correct 101 ms 55196 KB Output is correct
6 Correct 83 ms 51348 KB Output is correct
7 Correct 110 ms 55196 KB Output is correct
8 Correct 74 ms 46232 KB Output is correct
9 Correct 89 ms 49696 KB Output is correct
10 Correct 88 ms 49836 KB Output is correct
11 Correct 68 ms 42908 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 5 ms 384 KB Output is correct
38 Correct 5 ms 384 KB Output is correct
39 Correct 5 ms 384 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 5 ms 384 KB Output is correct
42 Correct 5 ms 384 KB Output is correct
43 Correct 5 ms 384 KB Output is correct
44 Correct 5 ms 384 KB Output is correct
45 Correct 5 ms 384 KB Output is correct
46 Correct 5 ms 384 KB Output is correct
47 Correct 5 ms 384 KB Output is correct
48 Correct 44 ms 384 KB Output is correct
49 Correct 5 ms 384 KB Output is correct
50 Correct 5 ms 384 KB Output is correct
51 Correct 5 ms 384 KB Output is correct
52 Correct 5 ms 384 KB Output is correct
53 Correct 5 ms 384 KB Output is correct
54 Correct 5 ms 384 KB Output is correct