Submission #481259

#	Time	Username	Problem	Language	Result	Execution time	Memory
481259		tranxuanbach	Three Friends (BOI14_friends)	C++17	100 / 100	164 ms	21136 KiB

friends

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());
int randt(int l, int r){
    return rando() % (r - l + 1) + l;
}

const int N = 2e6 + 5;
int base, mod;

inline void sadd(int& x, int y){
    if ((x += y) >= mod) x -= mod;
    return;
}

inline int add(int x, int y){
    if ((x += y) >= mod) x -= mod;
    return x;
}

inline void ssub(int& x, int y){
    if ((x -= y) < 0) x += mod;
    return;
}

inline int sub(int x, int y){
    if ((x -= y) < 0) x += mod;
    return x;
}

inline int mul(int x, int y){
    return 1ll * x * y % mod;
}

inline int binpow(int x, int y){
    int ans = 1;
    while (y){
        if (y & 1) ans = mul(ans, x);
        x = mul(x, x);
        y >>= 1;
    }
    return ans;
}

inline int inv(int x){
    return binpow(x, mod - 2);
}

#define div __div__
inline int div(int x, int y){
    return mul(x, binpow(y, mod - 2));
}

int fac[N], invfac[N];

void calfac(){
    fac[0] = invfac[0] = 1;
    For(i, 1, N){
        fac[i] = mul(fac[i - 1], i);
    }
    invfac[N - 1] = binpow(fac[N - 1], mod - 2);
    FordE(i, N - 2, 1){
        invfac[i] = mul(invfac[i + 1], i + 1);
    }
}

inline int C(int n, int k){
    if (n < 0 or k < 0 or k > n){
        return 0;
    }
    return mul(fac[n], mul(invfac[k], invfac[n - k]));
}

inline int P(int n, int k){
    if (n < 0 or k < 0 or k > n){
        return 0;
    }
    return mul(fac[n], invfac[n - k]);
}

bool isprime(int x){
    if (x <= 1){
        return 0;
    }
    if (x <= 3){
        return 1;
    }
    if (x % 2 == 0 or x % 3 == 0){
        return 0;
    }
    for (int i = 5; i * i <= x; i += 6){
        if (x % i == 0 or x % (i + 2) == 0){
            return 0;
        }
    }
    return 1;
}

int n;
string s;

#define hash __hash__

int powbase[N];
int hash[N];

int calhash(int l, int r){
    return sub(hash[r], mul(hash[l - 1], powbase[r - l + 1]));
}

int ans = -1, idxans = -1;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n;
    cin >> s; s = ' ' + s;
    if (n % 2 == 0){
        cout << "NOT POSSIBLE" << endl;
        return 0;
    }

    base = randt(1000, 100000);
    while (!isprime(base)){
        base++;
    }
    mod = randt(500000000, 1000000000);
    while (!isprime(mod)){
        mod++;
    }
    powbase[0] = 1;
    For(i, 1, N){
        powbase[i] = mul(powbase[i - 1], base);
    }
    ForE(i, 1, n){
        hash[i] = add(mul(hash[i - 1], base), s[i] - 'A' + 1);
    }
    int mid = n / 2 + 1;
    ForE(i, 1, n){
        if (i == mid){
            if (calhash(1, mid - 1) == calhash(mid + 1, n)){
                if (ans == -1){
                    ans = calhash(1, mid - 1);
                    idxans = i;
                }
                else if (ans != calhash(1, mid - 1)){
                    cout << "NOT UNIQUE" << endl;
                    return 0;
                }
            }
            continue;
        }
        if (i < mid){
            int val = add(mul(calhash(1, i - 1), powbase[mid - i]), calhash(i + 1, mid));
            if (val == calhash(mid + 1, n)){
                if (ans == -1){
                    ans = val;
                    idxans = i;
                }
                else if (ans != val){
                    cout << "NOT UNIQUE" << endl;
                    return 0;
                }
            }
        }
        else{
            int val = add(mul(calhash(mid, i - 1), powbase[n - i]), calhash(i + 1, n));
            if (val == calhash(1, mid - 1)){
                if (ans == -1){
                    ans = val;
                    idxans = i;
                }
                else if (ans != val){
                    cout << "NOT UNIQUE" << endl;
                    return 0;
                }
            }
        }
    }
    if (ans == -1){
        cout << "NOT POSSIBLE" << endl;
        return 0;
    }
    if (idxans <= mid){
        ForE(i, mid + 1, n){
            cout << s[i];
        } cout << endl;
    }
    else{
        ForE(i, 1, mid - 1){
            cout << s[i];
        } cout << endl;
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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