Submission #791560

#	Time	Username	Problem	Language	Result	Execution time	Memory
791560		Cookie	Three Friends (BOI14_friends)	C++14	100 / 100	138 ms	53216 KiB

friends

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define int long long
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ll mxn = 2e6 + 5, base = 972663749;
const ll mod = 911382323, inf = 1e9;
int n;
string s;
ll pw[mxn + 1], p[mxn + 1];
ll get(int l, int r){
    if(l > r)return(0);
    return((p[r + 1] - p[l] * pw[r - l + 1] + mod * mod) % mod);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    if(n % 2 == 0){
        cout << "NOT POSSIBLE";
        return(0);
    }
    pw[0] = 1;
    for(int i = 1; i <= n; i++){
        pw[i] = (pw[i - 1] * base) % mod;
    }
    for(int i = 1; i <= sz(s); i++){
        p[i] = (p[i - 1] * base + (s[i - 1] - 'A' + 1)) % mod;
    }
    int len = (n - 1) / 2;
    vt<ll>comp;
    for(int i = 0; i < sz(s); i++){
        ll s1, s2;
        if(i == 0){
            s1 = get(i + 1, i + len), s2 = get(i + len + 1, sz(s) - 1);
        }else if(i == len){
            s1 = get(0, len - 1), s2 = get(len + 1, sz(s) - 1);
        }else{
            if(i < len){
                s2 = get(n - len, n - 1); s1 = (get(0, i - 1) * pw[len - i] + get(i + 1, len)) % mod;
            }else{
                s1 = get(0, len - 1); s2 = (get(len, i - 1) * pw[sz(s) - 1 - i] + get(i + 1, sz(s) - 1)) % mod;
            }
        }
        
        if(s1 == s2){
            comp.pb(s1);
        }
        
    }
    sort(comp.begin(), comp.end()); comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    if(sz(comp) == 0)cout << "NOT POSSIBLE";
    else if(sz(comp) > 1)cout << "NOT UNIQUE";
    else{
        for(int i = 0; i + len - 1 < sz(s); i++){
            if(get(i, i + len - 1) == comp.back()){
                forr(j, i, i + len){
                    cout << s[j];
                }
                return(0);
            }
        }
        assert(0);
    }
    
    return(0);
}

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