oj.uz

Submission #48451

# Submission time Handle Problem Language Result Execution time Memory
48451 2018-05-13T16:15:50 Z someone_aa Three Friends (BOI14_friends) C++17
0 / 100
 79 ms 13448 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll p = 31LL;
const ll mod = 1000000007LL;
const int maxn = 200100;
ll pp[maxn], pref[maxn], n;
string code;

ll power(ll a, ll b) {
    // return a^b % mod
    if(b == 0LL) return 1LL;
    else if(b== 1LL) return a;
    else {
        if(b % 2 == 0) {
            ll half = power(a, b/2);
            return (half*half)%mod;
        }
        else if(b % 2 == 1) {
            ll half = power(a, b-1);
            return ((half)*a)%mod;
        }
    }
}

void get_consts() {
    pp[0] = 1LL;
    for(int i=1;i<maxn;i++) {
        pp[i] = pp[i-1] * p;
        pp[i] %= mod;
    }
}

void get_prefhash() {
    pref[0] = 0LL;
    for(int i=1;i<=n;i++) {
        pref[i] += pref[i-1];
        pref[i] += pp[i] * (code[i] - 'A' + 1LL);
        pref[i] %= mod;
    }
}

ll subhash(ll i, ll j) {
    ll tmp = 1LL * pref[j] + mod - pref[i-1];
    tmp %= mod;
    tmp *= 1LL * power(pp[i-1], mod-2);
    tmp %= mod;
    return 1LL * tmp;
}

ll mergehash(ll hasha, ll hashb, ll k) {
    //cout<<hasha<<" "<<hashb<<" "<<k<<"\n";
    ll temp = (hashb * pp[k])%mod;
    temp = temp + hasha;
    temp %= mod;
    //cout<<temp<<"\n";
    return temp;
}

int main() {
    get_consts();
    cin>>n;
    cin>>code; code = "#" + code;
    get_prefhash();
    if(n % 2 == 0) {
        cout<<"NOT POSSIBLE\n";
        return 0;
    }
    ll cnt = 0;
    ll answ = 0;


    for(int i=2;i<n;i++) {
       //cout<<i<<" -> ";
        if(i == n / 2 + 1) {
         //   cout<<"A\n";
            if(subhash(1, i-1) == subhash(i+1, n)) {
                cnt++;
                answ = i;
            }
        }
        else if( i < n/2+1) {
            if(mergehash(subhash(1, i-1), subhash(i+1, n/2+1), i-1) == subhash(n/2+2, n)) {
                cnt++;
                answ = i;
            }
        }
        else if ( i > n/2+1) {
            if(mergehash(subhash(n/2+1, i-1), subhash(i+1, n),(i-1)-(n/2+1)+1) == subhash(1, n/2)) {
                cnt++;
                answ = i;
            }
        }
    }

    if(subhash(2, n/2+1) == subhash(n/2+2, n)) {
        cnt++;
        answ = 1;
    }
    if(subhash(1, n/2) == subhash(n/2+1, n-1)) {
        cnt++;
        answ = n;
    }

    if(cnt == 0) {
        cout<<"NOT POSSIBLE\n";
    }
    else if(cnt == 1) {
        if(answ >= n/2+1) {
            for(int i=1;i<=n/2;i++) {
                cout<<code[i];
            }
        }
        else {
            for(int i=n/2+2;i<=n;i++) {
                cout<<code[i];
            }
        }
    }
    else {
        cout<<"NOT UNIQUE\n";
    }

    return 0;
}

Compilation message

friends.cpp: In function 'long long int power(long long int, long long int)':
friends.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1888 KB Output is correct
2 Correct 4 ms 2024 KB Output is correct
3 Correct 4 ms 2064 KB Output is correct
4 Correct 5 ms 2064 KB Output is correct
5 Correct 5 ms 2236 KB Output is correct
6 Correct 4 ms 2236 KB Output is correct
7 Correct 4 ms 2236 KB Output is correct
8 Correct 4 ms 2236 KB Output is correct
9 Correct 4 ms 2236 KB Output is correct
10 Correct 4 ms 2412 KB Output is correct
11 Correct 4 ms 2412 KB Output is correct
12 Correct 4 ms 2412 KB Output is correct
13 Correct 4 ms 2412 KB Output is correct
14 Correct 4 ms 2412 KB Output is correct
15 Correct 5 ms 2412 KB Output is correct
16 Correct 4 ms 2412 KB Output is correct
17 Correct 4 ms 2412 KB Output is correct
18 Correct 4 ms 2412 KB Output is correct
19 Correct 4 ms 2412 KB Output is correct
20 Correct 4 ms 2412 KB Output is correct
21 Correct 4 ms 2412 KB Output is correct
22 Correct 4 ms 2412 KB Output is correct
23 Correct 4 ms 2412 KB Output is correct
24 Correct 4 ms 2412 KB Output is correct
25 Correct 4 ms 2412 KB Output is correct
26 Correct 4 ms 2412 KB Output is correct
27 Correct 4 ms 2412 KB Output is correct
28 Correct 4 ms 2412 KB Output is correct
29 Correct 4 ms 2488 KB Output is correct
30 Correct 4 ms 2488 KB Output is correct
31 Correct 4 ms 2488 KB Output is correct
32 Correct 4 ms 2488 KB Output is correct
33 Correct 4 ms 2488 KB Output is correct
34 Correct 4 ms 2488 KB Output is correct
35 Correct 4 ms 2488 KB Output is correct
36 Correct 4 ms 2488 KB Output is correct
37 Correct 4 ms 2488 KB Output is correct
38 Correct 4 ms 2488 KB Output is correct
39 Correct 4 ms 2488 KB Output is correct
40 Correct 4 ms 2516 KB Output is correct
41 Correct 4 ms 2520 KB Output is correct
42 Correct 4 ms 2520 KB Output is correct
43 Correct 4 ms 2520 KB Output is correct
44 Correct 6 ms 2520 KB Output is correct
45 Correct 6 ms 2520 KB Output is correct
46 Correct 6 ms 2520 KB Output is correct
47 Correct 6 ms 2520 KB Output is correct
48 Correct 6 ms 2520 KB Output is correct
49 Correct 4 ms 2520 KB Output is correct
50 Incorrect 6 ms 2520 KB Output isn't correct
51 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 13448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -