Submission #222704

#	Time	Username	Problem	Language	Result	Execution time	Memory
222704		Bruteforceman	Three Friends (BOI14_friends)	C++11	100 / 100	110 ms	55196 KiB

friends

#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 / 35
• Subtask 2: 65 / 65