Submission #1352641

#TimeUsernameProblemLanguageResultExecution timeMemory
1352641hyyhThree Friends (BOI14_friends)C++20
0 / 100
129 ms34456 KiB
#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
#include <tuple>
#include <functional>

#define int long long

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
using piiii = tuple<int,int,int,int>;
#define endl '\n'
#define f first
#define s second
#define all(x) begin(x),end(x)

int const hash1 = 1e9+7;
int const hash2 = 1e9+9;

int n;
string str;

void print(int cur){
    string ans = "";
    while(cur > 0){
        ans += char((cur%26)+64);
        cur/=26;
    }
    reverse(all(ans));
    cout << ans << endl;
}

int expo(int a,int b,int md){
    if(b == 0) return 1;
    else if(b == 1) return a;
    else{
        int t = expo(a,b/2,md);
        if(b&1) return (((t*t)%md)*a)%md;
        else return ((t*t)%md);
    }
}

vector<int> find(int hash){
    vector<int> ans;
    vector<int> hashdp(n+1);
    hashdp[0] = 1;
    for(int i{1};i <= n;i++){
        hashdp[i] = (hashdp[i-1]*26)%hash;
    }
    auto add = [&](char c,int cur,int pos){
        int ret = cur;
        ret += hashdp[pos]*(c-64);
        ret %= hash;
        return ret;
    };
    vector<int> suff(n+1);
    int ans1st = 0;
    int md = n/2;
    for(int i{n-1};i > md;i--){
        ans1st = add(str[i],ans1st,n-i-1);
        suff[i] = ans1st;
    }
    int ans2st = 0;
    int cur2 = str[md]-64;
    suff[md] = cur2;
    for(int i{md-1};i >= 0;i--){
        ans2st = add(str[i],ans2st,md-i-1);
        cur2 = add(str[i],cur2,md-i);
        suff[i] = cur2;
    }
    suff[n] = 0;
    // print(ans1st);
    // print(ans2st);
    // for(int i{};i < n;i++){
    //     print(suff[i]);
    // }
    int frcur = 0;
    for(int i{};i < md;i++){
        int newval = (frcur*hashdp[md-i]+suff[i+1])%hash;
        // cout << i << endl;
        // print(newval);
        if(newval == ans1st) ans.emplace_back(i);
        frcur *= 26;
        frcur += (str[i]-64);
        frcur %= hash;
    }
    int sdcur = 0;
    for(int i{md};i < n;i++){
        int newval = (sdcur*hashdp[n-i-1]+suff[i+1])%hash;
        // cout << i << endl;
        // print(newval);
        if(newval == ans2st) ans.emplace_back(i);
        sdcur *= 26;
        sdcur += (str[i]-64);
        sdcur %= hash;
    }
    return ans;
}

signed main(){
    cin >> n;
    if(n%2 == 0){
        cout << "NOT POSSIBLE";
        return 0;
    }
    cin >> str;
    auto ans1 = find(hash1);
    auto ans2 = find(hash2);
    set<int> finale;
    for(auto k:ans1) finale.insert(k);
    for(auto k:ans2) finale.insert(k);
    if(finale.size() == 0){
        cout << "NOT POSSIBLE";
    }
    else if(finale.size() > 1){
        cout << "NOT UNIQUE";
    }
    else{
        int val = *finale.begin();
        int md = n/2;
        if(val < md){
            for(int i{};i <= md;i++){
                if(i == val) continue;
                cout << str[i];
            }
        }
        else{
            for(int i{md};i < n;i++){
                if(i == val) continue;
                cout << str[i];
            }
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...