Submission #1165795

#TimeUsernameProblemLanguageResultExecution timeMemory
1165795fryingducThree Friends (BOI14_friends)C++20
100 / 100
185 ms61388 KiB
#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e6 + 5;
const int mod[] = {1000000009, 141257};
const int base = 311;
int n;
string s;
int h[maxn][2], p[maxn][2];

void solve() {
  cin >> n >> s;
  if (n % 2 == 0) {
    cout << "NOT POSSIBLE\n";
    return;
  }
  s = ' ' + s;
  for (int c = 0; c < 2; ++c) {
    for (int i = 1; i <= n; ++i) {
      h[i][c] = ((1ll * h[i - 1][c] * base % mod[c]) + (s[i] - 'A' + 1)) % mod[c];
    }
  }
  auto get_hash = [&](int l, int r) {
    if (l > r) return make_pair(0, 0);
    int x[2];
    for (int c = 0; c < 2; ++c) {
      x[c] = (h[r][c] - (1ll * h[l - 1][c] * p[r - l + 1][c] % mod[c]) + mod[c]) % mod[c];
    }
    return make_pair(x[0], x[1]);
  };
  vector<int> pos;
  vector<pair<int, int>> hc;
  pair<int, int> ft = get_hash(n / 2 + 2, n);
  pair<int, int> se = make_pair(h[n / 2][0], h[n / 2][1]);
  for (int i = 1; i <= n; ++i) {
    pair<int, int> hh = (i <= n / 2 ? ft : se);
    pair<int, int> x = get_hash(1, i - 1), y = get_hash(i + 1, n);
    pair<int, int> rm;
    rm.first = (1ll * x.first * p[n - i][0] % mod[0] + y.first) % mod[0];
    rm.second = (1ll * x.second * p[n - i][1] % mod[1] + y.second) % mod[1];
    hh.first = (1ll * hh.first * p[n / 2][0] % mod[0] + hh.first) % mod[0];
    hh.second = (1ll * hh.second * p[n / 2][1] % mod[1] + hh.second) % mod[1];
    if (rm == hh) {
      pos.push_back(i);
      hc.push_back(hh);
    }
  }
  sort(hc.begin(), hc.end());
  hc.erase(unique(hc.begin(), hc.end()), hc.end());
  if (pos.empty()) {
    cout << "NOT POSSIBLE\n";
  } else if ((int)hc.size() > 1) {
    cout << "NOT UNIQUE\n";
  } else {
    s.erase(s.begin() + pos[0]);
    for (int i = 1; i <= n / 2; ++i) {
      cout << s[i];
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  for (int c = 0; c < 2; ++c) {
    p[0][c] = 1;
    for (int i = 1; i < maxn; ++i) {
      p[i][c] = 1ll * p[i - 1][c] * base % mod[c];
    }
  }
  solve();

  return 0;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...