Submission #1109457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109457		Kirill22	Three Friends (BOI14_friends)	C++17	100 / 100	89 ms	40552 KiB

friends

#include "bits/stdc++.h"
 
using namespace std;
 
const int mod = (int) 1e9 + 7, p = 10103;
 
void solve() {
    int n;
    string s;
    cin >> n >> s;
    if (n % 2 == 0) {
        cout << "NOT POSSIBLE\n";
        return;
    }
    s = s + s;
    vector<int> h(s.size() + 1), pw(s.size() + 1, 1);
    for (int i = 0; i < (int) s.size(); i++) {
        h[i + 1] = (h[i] * 1ll * p + s[i]) % mod;
        pw[i + 1] = pw[i] * 1ll * p % mod;
    }
    auto get = [&] (int l, int r) {
        if (l > r) {
            return 0;
        }
        int res = (h[r + 1] - h[l] * 1ll * pw[r - l + 1] % mod + mod) % mod;
        return res;
    };
    map<int, int> ans;
    for (int i = 0; i < n; i++) {
        if (get(i + 1, i + n / 2) == get(i + n / 2 + 1, i + n / 2 + n / 2)) {
            if (i >= n / 2) {
                ans[get(0, n / 2 - 1)] = i;
            } else {
                ans[get(n - n / 2, n - 1)] = i;
            }
        }
    }
    if (ans.empty()) {
        cout << "NOT POSSIBLE\n";
        return;
    }
    if ((int) ans.size() > 1) {
        cout << "NOT UNIQUE\n";
        return;
    }
    s.erase(s.begin() + ans.begin()->second);
    assert(s.substr(0, n / 2) == s.substr(n / 2, n / 2));
    cout << s.substr(0, n / 2) << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

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