Submission #713471

#	Time	Username	Problem	Language	Result	Execution time	Memory
713471		apple	Three Friends (BOI14_friends)	C++14	0 / 100	68 ms	35564 KiB

friends

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define INF ((ll)(1e9) + 7)
//#define INF (998244353ll)
#define N (int)(2e6 + 5)
using namespace std;
#define int ll
#define lsb(x) (x & (-x))
const int P = 31;

int n, k, g;
int po[N];
int h[N];

int f(int l, int r){
    if(r < l)return 0;
    if(l == 0)return h[r];
    return (h[r] - (h[l - 1] * po[r - l + 1]) % INF + INF) % INF;
}

int f2(int l, int r, int del){
    int h1 = f(l, del - 1);
    int h2 = f(del + 1, r);
    if(del == r){
        return h1;
    }
    return ((h1 * P) + h2) % INF;
}

void solve(){
    cin >> n;
    string s;
    cin >> s;

    po[0] = 1;
    h[0] = (s[0] - 'A') + 1;
    for(int i=1; i<n; i++){
        h[i] = (h[i - 1] * P + ((s[i] - 'A') + 1)) % INF;
        po[i] = po[i - 1] * P % INF;
    }

    int ind = -1;
    set<int> ss;


    for(int i=0; i<n; i++){
        int sts = 0, ends = 0;
        if(i >= n/2){
            sts = f(0, n/2 - 1);
        }
        else{
            sts = f2(0, n/2, i);
        }
        if(i <= n/2){
            ends = f(n/2 + 1, n - 1);
        }
        else{
            ends = f2(n/2, n - 1, i);
        }

        if(sts == ends){
            ss.insert(sts);
            ind = i;
        }
    }

    int ans = ss.size();
    if(ans == 0){
        cout << "NOT POSSIBLE";
    }
    else if(ans == 1){
        string res;
        for(int i=0; i<n && int(res.size()) < n/2; i++){
            if(i != ind)res += s[i];
        }
        cout << res;
    }
    else{
        cout << "NOT UNIQUE";
    }
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    //pre();
    for(int i=1; i<=T; i++){
        solve();
    }
}

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