Submission #1173275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173275		DangKhoizzzz	Three Friends (BOI14_friends)	C++17	0 / 100	2 ms	580 KiB

friends

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18 + 7;
const int maxn = 2e5 + 7;
const int base = 31;
const int mod = 1e9 + 7;

int n;
char s[maxn];
int prehash[maxn] , prepow[maxn];

void build()
{
    prepow[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        prehash[i] = (prehash[i-1]*base + (s[i] - 'A'))%mod;
        prepow[i] = (prepow[i-1] * base)%mod;
    }
}

int get(int l , int r)
{
    return (prehash[r] - prehash[l-1]*prepow[r - l + 1] + mod*mod)%mod;
}

int merge_hash(int l1 , int r1  , int l , int r)
{
    return (get(l1 , r1)*prepow[r - l + 1] + get(l , r))%mod;
}

int cnt = 0;
pii ans;

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];
    build();

    if(n%2 == 0) {cout << "NOT POSSIBLE" << '\n';return;}

    int mid = (n+1)/2;

    if(get(1 , mid-1) == get(mid+1 , n))
    {
        cnt = 1; ans = {1 , mid - 1};
    }
    if(get(2 , mid) == get(mid+1 , n))
    {
        if(cnt == 1) {cout << "NOT UNIQUE"; return;}
        cnt = 1; ans = {2 , mid};
    }
    if(get(1 , mid - 1) == get(mid , n-1))
    {
        if(cnt == 1) {cout << "NOT UNIQUE"; return;}
        cnt = 1; ans = {1 , mid - 1};
    }

    for(int del = 2; del < mid; del++)
    {
        if(merge_hash(1 , del - 1 , del + 1 , mid) == get(mid + 1 , n))
        {
            if(cnt == 1) {cout << "NOT UNIQUE"; return;}
            cnt = 1; ans = {mid+1 , n};
        }
    }
    for(int del = mid+1; del < n; del++)
    {
        if(get(1 , mid - 1) == merge_hash(mid , del - 1 , del + 1 , n))
        {
            if(cnt == 1) {cout << "NOT UNIQUE"; return;}
            cnt = 1; ans = {1 , mid - 1};
        }
    }

    if(cnt == 0) {cout << "NOT POSSIBLE" << '\n'; return;}

    for(int i = ans.fi; i <= ans.se; i++) cout << s[i];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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