Submission #309685

#	Time	Username	Problem	Language	Result	Execution time	Memory
309685		nicolaalexandra	Three Friends (BOI14_friends)	C++14	100 / 100	264 ms	66424 KiB

friends

#include <bits/stdc++.h>
#define DIM 2000010
#define MOD1 1000000007
#define MOD2 1000000009
using namespace std;

long long hash1[DIM],hash2[DIM],p1[DIM],p2[DIM];
map <pair<long long,long long>, int> f;
char s[DIM];
int n,i;

pair <long long,long long> get_hash (int x, int y){

    if (x > y)
        return make_pair (0,0);

    long long val1 = (hash1[y] - hash1[x-1] * p1[y-x+1] % MOD1 + MOD1) % MOD1;
    long long val2 = (hash2[y] - hash2[x-1] * p2[y-x+1] % MOD2 + MOD2) % MOD2;

    return make_pair (val1,val2);

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>s+1;

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

    for (i=1;i<=n;i++){
        hash1[i] = (hash1[i-1] * 30 + s[i] - 'A' + 1) % MOD1;
        hash2[i] = (hash2[i-1] * 30 + s[i] - 'A' + 1) % MOD2;
    }

    p1[0] = p2[0] = 1;
    for (i=1;i<=n;i++){
        p1[i] = 1LL * p1[i-1] * 30 % MOD1;
        p2[i] = 1LL * p2[i-1] * 30 % MOD2;
    }

    int lg = (n-1) / 2, sol = 0, poz = 0;

    for (i=1;i<=n;i++){
        if (i <= lg){

            pair <long long,long long> cod1 = get_hash (i+1,lg+1);
            long long val1 = (hash1[i-1] * p1[lg+1-i] % MOD1 + cod1.first) % MOD1;
            long long val2 = (hash2[i-1] * p2[lg+1-i] % MOD2 + cod1.second) % MOD2;

            pair <long long,long long> cod2 = get_hash (lg+2,n);

            if (val1 == cod2.first && val2 == cod2.second){
                if (!f[make_pair(val1,val2)])
                    sol++;
                f[make_pair(val1,val2)]++;
                poz = i;
            }


        } else {

            /// lg+1...i-1 + i+1...n
            pair <long long,long long> cod1 = get_hash (lg+1,i-1);
            pair <long long,long long> cod2 = get_hash (i+1,n);

            long long val1 = (cod1.first * p1[n-i] % MOD1 + cod2.first) % MOD1;
            long long val2 = (cod1.second * p2[n-i] % MOD2 + cod2.second) % MOD2;

            if (val1 == hash1[lg] && val2 == hash2[lg]){
                if (!f[make_pair(val1,val2)])
                    sol++;
                f[make_pair(val1,val2)]++;
                poz = i;
            }
        }
    }

    if (!sol){
        cout<<"NOT POSSIBLE";
        return 0;
    }

    if (sol > 1){
        cout<<"NOT UNIQUE";
        return 0;
    }

    for (i=1;i<=lg;i++){
        if (i == poz){
            lg++;
            continue;
        }
        cout<<s[i];
    }


    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     cin>>n>>s+1;
      |             ~^~

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