oj.uz

Submission #361966

# Submission time Handle Problem Language Result Execution time Memory
361966 2021-02-01T12:02:40 Z Ahmad_Hasan Three Friends (BOI14_friends) C++17
35 / 100
 500 ms 18192 KB 
#include <bits/stdc++.h>
#define int long long
/**
     ||||||||||       |||||     |||||    ||||||||||
    |||||||||||||     |||||     |||||  |||||
   ||||     ||||||    |||||     |||||  |||||
  |||||||||||||||||   |||||||||||||||    ||||||||||
 |||||||||||||||||||  |||||||||||||||           |||||
 |||||         |||||  |||||     |||||           |||||
 |||||         |||||  |||||     |||||    ||||||||||
AHMED;HASSAN;SAEED;
*/

using namespace std;
int mod=1e9+7;
int pwr(int b,int e=mod-2ll){
    int mul=b;
    int ret=1;
    while(e){
        if(e&1ll){
            ret*=mul;
            ret%=mod;
        }
        mul*=mul;
        mul%=mod;
        e>>=1;
    }
    return ret;
}


int prf[2000000+5];

int p=31;

int hsh(int l,int r){
    if(l>r)
        return 0;
    return ((((prf[r+1]-prf[l])%mod*pwr(pwr(p,l)))%mod+mod)%mod);
}


int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ppw=p;
    prf[0]=0ll;
    for(int i=0;i<n;i++){
        prf[i+1]=(prf[i]+ppw*(s[i]-'A'))%mod;
        prf[i+1]%=mod;
        ppw*=p;
        ppw%=mod;
    }
    int lst=-1;
    int cnt=0;
    unordered_map<int,int>mp;
    for(int i=0;i<n;i++){
        int hsh1=hsh(0,min(n/2,i)-1)+(hsh(i+1,n/2+(i<=n/2-1)-1)*pwr(p,min(n/2,i)))%mod;
        hsh1%=mod;
        int hsh2=hsh(n-(n/2)-(i>=n-(n/2)),i-1)+(hsh(max(i+1,n-(n/2)-(i>=n-(n/2))),n-1-(i==n-1))*pwr(p,max(0ll,i-(n-(n/2)-(i>=n-(n/2))))))%mod;
        hsh2%=mod;

        if(hsh1==hsh2){
            cnt++;
            lst=i;
            mp[hsh1]++;
        }
        ///cout<<hsh1<<' '<<hsh2<<'\n';

    }
    if(!cnt||n%2==0ll)
        cout<<"NOT POSSIBLE\n";
    else if(mp.size()>1)
        cout<<"NOT UNIQUE\n";
    else{
        for(int i=0;i<n/2+(lst<n/2);i++){
            if(i==lst)continue;
            cout<<s[i];
        }
    }
    return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 0 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 0 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 0 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 0 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 0 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 0 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 0 ms 364 KB Output is correct
34 Correct 0 ms 364 KB Output is correct
35 Correct 0 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 0 ms 364 KB Output is correct
38 Correct 0 ms 364 KB Output is correct
39 Correct 0 ms 364 KB Output is correct
40 Correct 0 ms 364 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 0 ms 364 KB Output is correct
43 Correct 1 ms 364 KB Output is correct
44 Correct 4 ms 492 KB Output is correct
45 Correct 4 ms 364 KB Output is correct
46 Correct 4 ms 364 KB Output is correct
47 Correct 4 ms 364 KB Output is correct
48 Correct 4 ms 364 KB Output is correct
49 Correct 4 ms 364 KB Output is correct
50 Correct 4 ms 364 KB Output is correct
51 Correct 4 ms 364 KB Output is correct
52 Correct 4 ms 384 KB Output is correct
53 Correct 4 ms 364 KB Output is correct
54 Correct 4 ms 364 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 18192 KB Time limit exceeded
2 Halted 0 ms 0 KB -