Submission #339258

#	Time	Username	Problem	Language	Result	Execution time	Memory
339258		nandonathaniel	Three Friends (BOI14_friends)	C++14	100 / 100	88 ms	22032 KiB

friends

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000005,MOD=1e9+7;

int pref[MAXN],pkt[MAXN];
set<int> S;

int get(int L,int R){
	L++;R++;
	if(L>R)return 0;
	return (pref[R]-((1LL*pref[L-1]*pkt[R-L+1])%MOD)+MOD)%MOD;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	string s;
	cin >> n >> s;
	if(n%2==0){
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	pkt[0]=1;
	for(int i=0;i<n;i++){
		pref[i+1]=(26LL*pref[i]+s[i]-'A')%MOD;
		pkt[i+1]=(26LL*pkt[i])%MOD;
	}
	int idxL,idxR;
	for(int i=1;i<n-1;i++){
		int kiri=0,kanan=0;
		if(i<=n/2){
			kiri=(((1LL*pkt[n/2-i]*get(0,i-1))%MOD)+get(i+1,i+n/2-i))%MOD;
			kanan=get(n/2+1,n-1);
		}
		else{
			kiri=get(0,n/2-1);
			kanan=(((1LL*pkt[n-i-1]*get(n/2,i-1))%MOD)+get(i+1,n-1))%MOD;
		}
		if(kiri==kanan){
			S.insert(kiri);
			if(i<=n/2){
				idxL=n/2+1;idxR=n-1;
			}
			else{
				idxL=0;idxR=n/2-1;
			}
		}
	}
	int kiri=get(1,n/2),kanan=get(n/2+1,n-1);
	if(kiri==kanan){
		S.insert(kiri);
		idxL=1;idxR=n/2;
	}
	kiri=get(0,n/2-1);kanan=get(n/2,n-2);
	if(kiri==kanan){
		S.insert(kiri);
		idxL=0;idxR=n/2-1;
	}
	if(S.size()==0){
		cout << "NOT POSSIBLE\n";
	}
	else if(S.size()==1){
		cout << s.substr(idxL,idxR-idxL+1) << '\n';
	}
	else cout << "NOT UNIQUE\n";
	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:63:29: warning: 'idxR' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |   cout << s.substr(idxL,idxR-idxL+1) << '\n';
      |                         ~~~~^~~~~
friends.cpp:63:19: warning: 'idxL' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |   cout << s.substr(idxL,idxR-idxL+1) << '\n';
      |           ~~~~~~~~^~~~~~~~~~~~~~~~~~

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