제출 #222703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222703		Bruteforceman	세 명의 친구들 (BOI14_friends)	C++11	35 / 100	1050 ms	41444 KiB

friends

#include <bits/stdc++.h>
using namespace std;
string s;
const int mod = 100000000 + 7;
const int base = 131;

long long modpow(int b, int e) {
  if(e == 0) return 1;
  if(e & 1) return (modpow(b, e - 1) * b) % mod;
  long long m = modpow(b, e >> 1);
  return (m * m) % mod;
}

int main() {
  int n;
  cin >> n >> s;
  n = s.size();
  int sz = (n - 1) / 2;
  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 * (modpow(base, 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 += modpow(base, i) * s[i];
    var %= mod;
  }
 
  var = 0;
  for(int i = n - 1; i >= 0; i--) {
    suf[i] = var;
    if(i == 0) break;
    var += modpow(base, 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.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: 0 / 65