Submission #726083

#	Time	Username	Problem	Language	Result	Execution time	Memory
726083		Tigerpants	Three Friends (BOI14_friends)	C++17	100 / 100	197 ms	36576 KiB

friends

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>
#include <set>
#include <map>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef string str;
typedef vector<str> vstr;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define sz(a) a.size()

ll p = 1000000093;
vll x;
vll x_inv;

ll ord(char c) {return 1 + (int) c - (int) 'A';}
char chr(ll v) {return (char) (v - 1 + (int) 'A');}

struct HashedString {
    ll H;
    ll L;

    void reset_mod() {
        H = ((H % p) + p) % p;
    }

    void append(char c) {
        H += ord(c) * x[L];
        L++;
        reset_mod();
    }
    void prepend(char c) {
        H *= x[1];
        H += ord(c);
        L++;
        reset_mod();
    }
    void pop_back(char c) {
        L--;
        H -= ord(c) * x[L];
        reset_mod();
    }
    void pop_front(char c) {
        H -= ord(c);
        L--;
        H *= x_inv[1];
        reset_mod();
    }

    void append(HashedString s) {
        H += s.H * x[L];
        L += s.L;
        reset_mod();
    }
    void prepend(HashedString s) {
        H *= x[s.L];
        H += s.H;
        L += s.L;
        reset_mod();
    }
    void pop_back(HashedString s) {
        L -= s.L;
        H -= s.H * x[L];
        reset_mod();
    }
    void pop_front(HashedString s) {
        H -= s.H;
        L -= s.L;
        H *= x_inv[s.L];
        reset_mod();
    }
};
// s[0] * x[0] + s[1] * x[1] + s[2] * x[2] + s[3] * x[3] + ... + s[L - 1] * x[L - 1]

ll N;
str U;
ll M;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    cin >> U;

    M = (N - 1) / 2;

    if (2 * M + 1 != N) {
        cout << "NOT POSSIBLE" << endl;
        return 0;
    }

    x.resize(N);
    x_inv.resize(N);
    x[0] = 1;
    x_inv[0] = 1;
    rep(i, 1, N) {
        x[i] = (x[i - 1] * 537824) % p;
        x_inv[i] = (x_inv[i - 1] * 308046899) % p;
    }

    map<ll, ll> answ;

    // for each i, we check if (U[:i - 1] + U[i:])[:N//2] == (U[:i - 1] + U[i:])[N//2:]

    HashedString a = {.H = 0, .L = 0};
    HashedString b = {.H = 0, .L = 0};
    HashedString c = {.H = 0, .L = 0};

    // check i <= M
    rep(j, 0, M) {
        b.append(U[j + 1]);
        c.append(U[M + j + 1]);
    }
    if (b.H == c.H) answ[b.H] = 0;
    rep(i, 1, M + 1) {
        a.append(U[i - 1]);
        b.pop_front(U[i]);

        b.prepend(a);
        if (b.H == c.H) answ[b.H] = i;
        b.pop_front(a);
    }
    // a = [0, M - 1]
    // b = [0, 0]
    // c = [M + 1, 2M + 1]

    // check i > M
    rep(i, M + 1, 2 * M + 1) {
        b.append(U[i - 1]);
        c.pop_front(U[i]);

        b.append(c);
        if (b.H == a.H) answ[b.H] = i;
        b.pop_back(c);
    }

    if (sz(answ) == 0) {
        cout << "NOT POSSIBLE" << endl;
    } else if (sz(answ) == 1) {
        //cout << answ[0] << endl;
        if (answ.begin()->second >= M) {
            rep(i, 0, M) {
                cout << U[i];
            }
            cout << endl;
        } else {
            rep(i, M + 1, 2 * M + 1) {
                cout << U[i];
            }
            cout << endl;
        }
    } else {
        cout << "NOT UNIQUE" << endl;
    }

    return 0;
}

// use string hashing
// represent string by length and polynomial evaluated mod 10^9 + 93

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