Submission #41336

#	Time	Username	Problem	Language	Result	Execution time	Memory
41336		gabrielsimoes	Three Friends (BOI14_friends)	C++14	0 / 100	1072 ms	18420 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 BASE = 37;

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;

  buildHash();

  vector<int> ans;

  if (getHash(1, m) == getHash(m + 1, n - 1)) ans.push_back(0);
  if (getHash(0, m - 1) == getHash(m, n - 2)) ans.push_back(n - 1);
  if (getHash(0, m - 1) == getHash(m + 1, n - 1)) ans.push_back(m);

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

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

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

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