Submission #1108492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108492		nasir_bashirov	Three Friends (BOI14_friends)	C++11	0 / 100	649 ms	53228 KiB

friends

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define int long long

const int sz = 2e6 + 5;
const int mod = 1e9 + 7;

int pw[sz], inv[sz], pre[sz], n;
string s;

int sum(int a, int b){
    return (a + b) % mod;
}

int mult(int a, int b){
    return a % mod * (b % mod) % mod;
}

int sub(int a, int b){
    return (a + mod - b) % mod;
}

int binpow(int a, int b){
    if(b == 0)  return 1;
    if(b & 1)   return (a % mod * binpow(a, b - 1)) % mod;
    return binpow(a * a % mod, b / 2) % mod;
}

int get_hash(int l, int r){
    return mult(sub(pre[r], pre[l - 1]), inv[l - 1]);
}

void fmain(){
    fastio;
    cin >> n >> s;
    s = ' ' + s;
    pw[0] = inv[0] = 1;
    for(int i = 1; i <= n; i++){
        pw[i] = mult(pw[i - 1], 29);
        inv[i] = binpow(pw[i], mod - 2);
        pre[i] = sum(pre[i - 1], mult(s[i] - 'A' + 1, pw[i]));
    }
    int f = 0;
    int k = n / 2, lst = -1;
    for(int i = 1; i <= n; i++){
        int s1 = get_hash(1, i - 1), s2 = get_hash(i + 1, n);
        // cout << "before : " << s1 << " " << s2 << endl;
        if(i <= k){
            int m = k - i + 1;
            s1 = sum(s1, mult(get_hash(i + 1, i + m), pw[i - 1]));
            s2 = mult(sub(s2, get_hash(i + 1, i + m)), inv[m]);
        }
        else{
            int m = k - (n - i);
            s1 = sub(s1, mult(get_hash(i - m, i - 1), pw[i - m - 1]));
            s2 = sum(get_hash(i - m, i - 1), mult(s2, pw[m]));
        }
        // cout << s1 << " " << s2 << endl;
        if(s1 == s2)    lst = i, f = (f == 1 or f == -1 ? -1 : 1);
        // cout << "After : " << s1 << " " << s2 << endl;
    }
    if(f == 0)  cout << "NOT POSSIBLE";
    else if(f == -1)  cout << "NOT UNIQUE";
    else{
        // cout << lst << endl;
        string ans = "";
        if(lst <= k){
            for(int i = 1; i < lst; i++)ans += s[i];
            for(int i = 1; i <= k - lst + 1; i++)   ans += s[lst + i];
        }
        else{
            for(int i = 1; i <= k; i++){
                ans += s[i];
            }
        }
        cout << ans;
    }
    // 1, 2 i = 3 4, 5, 6, 7, 8, 9, 10, 11
}
 
signed main(){
    int tmr = 1;
    // cin >> tmr;
    while(tmr--){
        fmain();
    }
}

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