oj.uz

Submission #226439

# Submission time Handle Problem Language Result Execution time Memory
226439 2020-04-23T19:40:43 Z MKopchev Three Friends (BOI14_friends) C++14
100 / 100
 189 ms 21904 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e6+42,base=31,mod=1e9+9;

string inp;

string outp;

int n,sz;

int st[nmax],pref[nmax];

set<int> seen;

int ask(int l,int r)
{
    if(l>r)return 0;

    long long help=pref[r];

    long long sub=0;
    if(l)sub=pref[l-1];

    sub=sub*st[r-l+1]%mod;

    //cout<<"ask "<<l<<" "<<r<<" -> "<<((help-sub)%mod+mod)%mod<<endl;

    return ((help-sub)%mod+mod)%mod;
}

bool been_0=0,been_n=0;

void pick(int l,int r)
{
    if(l==0&&been_0)return;
    if(l==n+1&&been_n)return;

    string help="";

    for(int i=l;i<=r;i++)
        help.push_back(inp[i]);

    if(outp.size())
    {
        if(help!=outp)
        {
            cout<<"NOT UNIQUE"<<endl;
            exit(0);
        }
    }

    outp=help;

    if(l==0)been_0=1;
    if(l==n+1)been_n=1;
}
int main()
{
    scanf("%i",&sz);

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

    for(int i=0;i<sz;i++)
    {
        char c=getchar();
        while('A'>c||c>'Z')c=getchar();
        inp.push_back(c);
    }

    n=(sz-1)/2;

    pref[0]=inp[0]-'A';

    for(int i=1;i<sz;i++)
        pref[i]=(1LL*pref[i-1]*base+inp[i]-'A')%mod;

    st[0]=1;
    for(int i=1;i<sz;i++)st[i]=1LL*st[i-1]*base%mod;

    int mem=ask(n+1,sz-1);
    //in the first half
    for(int i=0;i<=n;i++)
    {
        //cut i-th
        long long part1=1LL*pref[i-1]*st[n-i];

        long long part2=ask(i+1,n);

        part1=(part1+part2)%mod;

        //cout<<part1<<" "<<ask(n+1,sz-1)<<endl;

        if(part1==mem)
            pick(n+1,sz-1);
    }

    mem=ask(0,n-1);
    //in the second half
    for(int i=n;i<sz;i++)
    {
        //cut i-th
        long long part1=1LL*ask(n,i-1)*st[sz-1-i];

        long long part2=ask(i+1,sz-1);

        part1=(part1+part2)%mod;

        //cout<<part1<<" "<<ask(0,n-1)<<endl;

        if(part1==mem)
            pick(0,n-1);
    }

    if(outp.size())
    {
        for(auto k:outp)
            printf("%c",k);
        printf("\n");
    }
    else cout<<"NOT POSSIBLE"<<endl;
    return 0;
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&sz);
     ~~~~~^~~~~~~~~~

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 21856 KB Output is correct
2 Correct 165 ms 21904 KB Output is correct
3 Correct 189 ms 21856 KB Output is correct
4 Correct 160 ms 21856 KB Output is correct
5 Correct 164 ms 21856 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 168 ms 21832 KB Output is correct
8 Correct 111 ms 20712 KB Output is correct
9 Correct 142 ms 20668 KB Output is correct
10 Correct 143 ms 20840 KB Output is correct
11 Correct 91 ms 16872 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 4 ms 384 KB Output is correct
33 Correct 4 ms 384 KB Output is correct
34 Correct 5 ms 304 KB Output is correct
35 Correct 4 ms 256 KB Output is correct
36 Correct 4 ms 256 KB Output is correct
37 Correct 5 ms 256 KB Output is correct
38 Correct 5 ms 384 KB Output is correct
39 Correct 4 ms 384 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 5 ms 384 KB Output is correct
42 Correct 5 ms 384 KB Output is correct
43 Correct 4 ms 384 KB Output is correct
44 Correct 4 ms 384 KB Output is correct
45 Correct 4 ms 384 KB Output is correct
46 Correct 5 ms 384 KB Output is correct
47 Correct 4 ms 384 KB Output is correct
48 Correct 5 ms 384 KB Output is correct
49 Correct 4 ms 384 KB Output is correct
50 Correct 4 ms 384 KB Output is correct
51 Correct 4 ms 384 KB Output is correct
52 Correct 4 ms 384 KB Output is correct
53 Correct 5 ms 384 KB Output is correct
54 Correct 4 ms 384 KB Output is correct