제출 #41343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41343		gabrielsimoes	세 명의 친구들 (BOI14_friends)	C++14	35 / 100	1074 ms	18260 KiB

friends

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const string not_possible = "NOT POSSIBLE";
const string not_unique = "NOT UNIQUE";

// const ll MOD = 1645333507;
const ll MOD = 15485867;
const ll BASE = 137;

int n, m;
string s;

ll mod(ll x) {
  x %= MOD;
  if (x < 0)
    return x + MOD;
  else
    return x;
}

ll append(ll prev, char a) { return mod(prev * BASE + ll(a - 'A')); }

ll fastpow(ll x, ll pot) {
  ll result = 1;
  ll current = x;

  while (pot != 0) {
    if (pot & 1) result = mod(result * current);
    current = mod(current * current);
    pot >>= 1;
  }

  return result;
}

vector<ll> h;

void buildHash() {
  h.resize(n);
  for (int i = 0; i < n; i++) {
    h[i] = append(i > 0 ? h[i - 1] : 0, s[i]);
  }
}

ll getHash(int i, int j) {
  ll result = mod(h[j] - (i > 0 ? h[i - 1] : 0) * fastpow(BASE, j - i + 1));
  return result;
}

ll getHash(int a, int b, int c, int d) {
  ll result = mod(getHash(a, b) * fastpow(BASE, d - c + 1) + getHash(c, d));
  return result;
}

int main() {
  cin >> n >> s;
  m = n / 2;

  if (n < 3 || n != m * 2 + 1) {
    cout << not_possible << endl;
    return 0;
  }

  buildHash();

  map<ll, int> ans;

  if (getHash(1, m) == getHash(m + 1, n - 1)) ans[getHash(1, m)] = 0;
  if (getHash(0, m - 1) == getHash(m + 1, n - 1)) ans[getHash(0, m - 1)] = m;
  if (getHash(0, m - 1) == getHash(m, n - 2)) ans[getHash(0, m - 1)] = n - 1;

  for (int i = 1; i < m; i++) {
    if (getHash(0, i - 1, i + 1, m) == getHash(m + 1, n - 1))
      ans[getHash(m + 1, n - 1)] = i;
  }

  for (int i = m + 1; i < n - 1; i++) {
    if (getHash(0, m - 1) == getHash(m, i - 1, i + 1, n - 1))
      ans[getHash(0, m - 1)] = i;
  }

  if (ans.size() == 0)
    cout << not_possible << endl;
  else if (ans.size() > 1)
    cout << not_unique << endl;
  else
    cout << s.substr(ans.begin()->second < m ? m + 1 : 0, m) << endl;
}

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