Submission #713943

#	Time	Username	Problem	Language	Result	Execution time	Memory
713943		Stickfish	Three Friends (BOI14_friends)	C++17	100 / 100	80 ms	28768 KiB

friends

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> z_function(string s) {
    int n = s.size();
    vector<int> ans(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i < r) {
            ans[i] = min(r - i, ans[i - l]);
        }
        while (i + ans[i] < n && s[i + ans[i]] == s[ans[i]])
            ++ans[i];
        if (r < i + ans[i]) {
            l = i;
            r = i + ans[i];
        }
    }
    return ans;
}

signed main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (n % 2 == 0) {
        cout << "NOT POSSIBLE\n";
        return 0;
    }
    vector<int> zs = z_function(s);
    reverse(s.begin(), s.end());
    vector<int> rzs = z_function(s);
    reverse(s.begin(), s.end());
    reverse(rzs.begin(), rzs.end());
    vector<int> ans;
    int m = n / 2;
    for (int i = 0; i < m; ++i) {
        if (zs[m + 1] >= i && rzs[m] >= m - i)
            ans.push_back(i);
    }
    if (s.substr(0, m) == s.substr(m + 1, m))
        ans.push_back(m);
    for (int i = m + 1; i < n; ++i) {
        if (zs[m] >= i - m && rzs[m - 1] >= n - i - 1)
            ans.push_back(i);
    }
    if (ans.empty()) {
        cout << "NOT POSSIBLE\n";
        return 0;
    }
    if ((ans[0] < m) != (ans.back() < m) && s.substr(0, m) != s.substr(m + 1, m)) {
        cout << "NOT UNIQUE\n";
        return 0;
    }
    s.erase(s.begin() + ans[0]);
    cout << s.substr(0, n / 2);
}

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