Submission #1066641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066641		giaminh2211	Three Friends (BOI14_friends)	C++14	100 / 100	83 ms	50228 KiB

friends

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int n;
const int base=37;
const int mod=1e9+7;
const int N=2e6+13;
ll f[N];
string a;
ll lt[N];
vector<int> v;
set<ll> s;

ll gethash(int l, int r){
    ll val=f[r]-f[l-1]*lt[r-l+1];
    val %= mod;
    while(val < 0) val += mod;
    return val;
}

ll getcon(int l, int r, int x, int y){
    ll val=gethash(l, r) * lt[y-x+1];
    val %= mod;
    val += gethash(x, y);
    val %= mod;
    return val;
}

void scan(){
    cin >> n >> a;
    if(n%2==0){
        cout << "NOT POSSIBLE";
        exit(0);
    }
    a=' '+a;
    lt[0]=1;
    for(int i=1; i<=n; i++){
        lt[i]=lt[i-1]*base%mod;
        f[i]=f[i-1] * base + (a[i]-'A'+1);
        f[i]%=mod;
    }
}

void solve(){
    for(int i=1; i<=n/2; i++){
        if(getcon(1, i-1, i+1, n/2+1)==gethash(n/2+2, n)){
            v.push_back(i);
            s.insert(gethash(n/2+2, n));
        }
    }
    if(gethash(1, n/2)==gethash(n/2+2, n)){
        v.push_back(n/2+1);
        s.insert(gethash(n/2+2, n));
    }
    for(int i=n/2+2; i<=n; i++){
        if(gethash(1, n/2)==getcon(n/2+1, i-1, i+1, n)){
            v.push_back(i);
            s.insert(gethash(1, n/2));
        }
    }
    if(v.size()==0) cout << "NOT POSSIBLE";
    else if(s.size() != 1){
    	cout << "NOT UNIQUE";
    }
    else{
    	string cc=" ";
        int id=v[0];
        for(int i=1; i<id; i++) cc+=a[i];
        for(int i=id+1; i<=n; i++) cc+=a[i];
        for(int i=1; i<=cc.size()/2; i++) cout << cc[i];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

Compilation message (stderr)

friends.cpp: In function 'void solve()':
friends.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i=1; i<=cc.size()/2; i++) cout << cc[i];
      |                      ~^~~~~~~~~~~~~

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