Submission #762540

#	Time	Username	Problem	Language	Result	Execution time	Memory
762540		BidoTeima	Three Friends (BOI14_friends)	C++17	0 / 100	306 ms	52320 KiB

friends

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1e9 + 9;
ll mul(ll a, ll b){
    return a % mod * (b % mod) % mod;
}
ll add(ll a, ll b){
    return (a + b) % mod;
}
ll sub(ll a, ll b){
    return (a + mod - b) % mod;
}
ll binexp(ll a, ll b){
    if(!b)
        return 1;
    ll ret = 1;
    while(b){
        if(b & 1)
            ret = mul(ret, a);
        b>>=1;
        a = mul(a, a);
    }
    return ret;
}
ll modinv(ll a){
    return binexp(a, mod - 2);
} 
#define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
#define combine(hash1, hash2, v) add(mul(hash2, v), hash1)
int main()
{ 
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    int n,cnt=0;
    string s;
    cin>>n>>s;
    if(n == 1 || n % 2 == 0){
        return cout<<"NOT POSSIBLE", 0;
    }
    ll p = 31, pw = 1;
    ll hash[n],inv[n],c[n];
    inv[0]=1;
    inv[1] = modinv(p);
    for(int i = 0; i < n; i++){
        c[i] = pw;
        hash[i] = mul(s[i] - 'A' + 1, pw);
        if(i)hash[i] = add(hash[i], hash[i - 1]);
        pw=mul(pw,p);
        if(i >= 2)inv[i]=mul(inv[1],inv[i-1]);
    }
    int l = -1, r = -1, rev = 0;
    for(int i = 0; i < n / 2; i++){
        ll val1,val2=val(hash, n / 2 + 1, n - 1);
        if(i == 0){
            val1 = val(hash, i + 1, n / 2);
        }else{
            val1 = combine(val(hash, 0, i - 1), val(hash, i + 1, n / 2), c[i]);
        } 
        if(val1==val2){
            l = n / 2 + 1, r = n - 1;
            ++cnt;
        }
    }  
    if(val(hash, 0, n / 2 - 1) == val(hash, n / 2 + 1, n - 1))++cnt, l = 0, r = n / 2 - 1;
    reverse(s.begin(), s.end());
    inv[0]=1;
    inv[1] = modinv(p);
    pw=1;
    for(int i = 0; i < n; i++){
        c[i] = pw;
        hash[i] = mul(s[i] - 'A' + 1, pw);
        if(i)hash[i] = add(hash[i], hash[i - 1]);
        pw=mul(pw,p);
        if(i >= 2)inv[i]=mul(inv[1],inv[i-1]);
    }
    for(int i = 0; i < n / 2; i++){
        ll val1,val2=val(hash, n / 2 + 1, n - 1);
        if(i == 0){
            val1 = val(hash, i + 1, n / 2);
        }else{
            val1 = combine(val(hash, 0, i - 1), val(hash, i + 1, n / 2), c[i]);
        } 
        if(val1==val2){
            l = n / 2 + 1, r = n - 1, rev = 1;
            ++cnt;
        }
    }  
    if(cnt == 0){
        cout<<"NOT POSSIBLE";
    }
    else if(cnt == 1){
        if(!rev){
            reverse(s.begin(),s.end());
            for(int i = l; i <= r; i++)cout<<s[i];
        }
        else{
            for(int i = r; i >= l; i--)cout<<s[i];
        }
    }
    else{
        cout<<"NOT UNIQUE";
    }
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
   29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
      |                                          ^
friends.cpp:53:22: note: in expansion of macro 'val'
   53 |         ll val1,val2=val(hash, n / 2 + 1, n - 1);
      |                      ^~~
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
   29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
      |                                          ^
friends.cpp:64:35: note: in expansion of macro 'val'
   64 |     if(val(hash, 0, n / 2 - 1) == val(hash, n / 2 + 1, n - 1))++cnt, l = 0, r = n / 2 - 1;
      |                                   ^~~
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
   29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
      |                                          ^
friends.cpp:77:22: note: in expansion of macro 'val'
   77 |         ll val1,val2=val(hash, n / 2 + 1, n - 1);
      |                      ^~~

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