Submission #645761

#	Time	Username	Problem	Language	Result	Execution time	Memory
645761		tvladm2009	Three Friends (BOI14_friends)	C++14	100 / 100	156 ms	67872 KiB

friends

#include <bits/stdc++.h>
#define int ll

using ll = long long;

int const nmax = 2000001;
int const B = 257;
int const P = 1e9 + 7;

int powerb[1 + nmax];
int pref[2][1 + nmax], suff[2][1 + nmax], solution[1 + nmax];

signed main() {
  int n;
  std::string s;
  std::cin >> n >> s;
  if(n % 2 == 0) {
    std::cout << "NOT POSSIBLE";
    return 0;
  }

  powerb[0] = 1;
  for(int i = 1;i <= nmax; i++)
    powerb[i] = 1LL * powerb[i - 1] * B % P;
  int half = n / 2;
  for(int i = 1;i <= half; i++)
    pref[0][i] = (pref[0][i - 1] * B + s[i - 1]) % P;
  for(int i = half;0 < i; i--)
    suff[0][i] = (suff[0][i + 1] + s[i - 1] * powerb[half - i]) % P;
  for(int i = half + 1;i <= n; i++)
    pref[1][i] = (pref[1][i - 1] * B + s[i - 1]) % P;
  for(int i = n;half < i; i--)
    suff[1][i] = (suff[1][i + 1] + s[i - 1] * powerb[n - i]) % P;
  int pos = 0;
  for(int i = 1;i <= n; i++) {
    int prefix = 0;
    int suffix = 0;
    if(i <= half) {
      prefix = (pref[0][i - 1] * powerb[half - i + 1] % P + (suff[0][i + 1] * B + s[half]) % P) % P;
      suffix = suff[1][n - half + 1];
    } else {
      prefix = pref[0][half];
      suffix = (pref[1][i - 1] * powerb[n - i] + suff[1][i + 1]) % P;
    }
    if(prefix == suffix) {
      if(pos > 0 && prefix != solution[pos]) {
        std::cout << "NOT UNIQUE\n";
        return 0;
      }
      solution[i] = prefix;
      pos = i;
    }
  }

  if(pos == 0) {
    std::cout << "NOT POSSIBLE";
    return 0;
  }
  if(pos <= half) {
    for(int i = n - half;i < n; i++)
      std::cout << s[i];
  } else {
    for(int i = 0;i < half; i++)
      std::cout << s[i];
  }
  return 0;
}

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