제출 #1165783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165783		fryingduc	Three Friends (BOI14_friends)	C++20	0 / 100	117 ms	34800 KiB

friends

#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, 998244353};
const int base = 31;
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;
  for (int i = 1; i <= n; ++i) {
    pair<int, int> hh;
    if (i <= n / 2) {
      hh = get_hash(n / 2 + 2, n);
    } else {
      hh = make_pair(h[n / 2][0], h[n / 2][1]);
    }
    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);
    }
  }
  if (pos.empty()) {
    cout << "NOT POSSIBLE\n";
  } else if ((int)pos.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;
}

• Subtask 1: 0 / 35
• Subtask 2: 0 / 65