Submission #196872

#	Time	Username	Problem	Language	Result	Execution time	Memory
196872		jovan_b	Three Friends (BOI14_friends)	C++17	100 / 100	113 ms	22952 KiB

friends

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int n, len;
 
const int MOD = 1000000007;
const int p = 31;
 
int hs[2000005];
 
int add(int a, int b){
    return (a+b)%MOD;
}
 
int mul(int a, int b){
    return (1LL*a*b)%MOD;
}
 
int pw(int a, int b){
    if(b == 0) return 1;
    int res = pw(a, b/2);
    res = mul(res, res);
    if(b%2) res = mul(res, a);
    return res;
}
 
int powers[2000005];
 
int substring_hash(int l, int r){
    if(l == 0) return hs[r];
    /*cout << hs[r] << endl;
    cout << hs[l-1] << endl;*/
    return add(hs[r], mul(powers[r-l+1], MOD - hs[l-1]));
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;
 
    cin >> n;
    if(n%2 == 0){
        cout << "NOT POSSIBLE\n";
        return 0;
    }
    powers[0] = 1;
    len = n/2;
    for(int i=1; i<=2000002; i++){
        powers[i] = mul(p, powers[i-1]);
    }
    string s;
    cin >> s;
    hs[0] = (s[0]-'A') + 1;
    for(int i=1; i<n; i++){
        hs[i] = add(mul(p, hs[i-1]), (s[i]-'A') + 1);
    }
    //cout << substring_hash(4, 6) << endl;
    //return 0;
    string res = "nema";
    int hashres = -500;
    int inv = pw(p, MOD-2);
    for(int i=0; i<len; i++){
        int a = 0;
        if(i) a = add(a, substring_hash(0, i-1));
        a = add(mul(a, powers[len-i]), substring_hash(i+1, len));
        int b = substring_hash(len+1, n-1);
        if(a == b){
            if(b == hashres) continue;
            if(res == "nema"){
                res = "";
                for(int j=len+1; j<n; j++) res += s[j];
                hashres = b;
            }
            else{
                cout << "NOT UNIQUE\n";
                return 0;
            }
        }
    }
    for(int i=len+1; i<n; i++){
        int a = substring_hash(0, len-1);
        int b = substring_hash(len, i-1);
        if(i != n-1) b = add(mul(b, powers[n-i-1]), substring_hash(i+1, n-1));
        if(a == b){
            if(a == hashres) continue;
            if(res == "nema"){
                res = "";
                for(int j=0; j<len; j++) res += s[j];
                hashres = a;
            }
            else{
                cout << "NOT UNIQUE\n";
                return 0;
            }
        }
    }
    int a = substring_hash(0, len-1);
    int b = substring_hash(len+1, n-1);
    //cout << a << " " << b << endl;
    if(a == b){
        if(a == hashres){
 
        }
        else if(res == "nema"){
            res = "";
            for(int j=0; j<len; j++) res += s[j];
            hashres = a;
        }
        else{
            cout << "NOT UNIQUE\n";
            return 0;
        }
    }
    if(res == "nema"){
        cout << "NOT POSSIBLE\n";
    }
    else cout << res << "\n";
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:64:9: warning: unused variable 'inv' [-Wunused-variable]
     int inv = pw(p, MOD-2);
         ^~~

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