Submission #957526

#	Time	Username	Problem	Language	Result	Execution time	Memory
957526		YassirSalama	Three Friends (BOI14_friends)	C++17	35 / 100	12 ms	12800 KiB

friends

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define md 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
const int MOD1=1e9+7,P=37;
int binpow(int a,int b,int mod){
	int res=1;
	while(b){
		if(b&1) res=(res%mod*a%mod)%mod;
		a=(a%mod*a%mod)%mod;
		b>>=1;
	}
	return res%mod;
}
int invmod(int a,int mod){
	return binpow(a,mod-2,mod);
}
int pref1[MAXN];
int inv1[MAXN];
const int MOD2=1404543827;
const int P2=83;
int pref2[MAXN];
int inv2[MAXN];
int sum1(int l,int r){
	if(l==0) return pref1[r]%MOD1;
	else 
		return ((pref1[r]-(ll)pref1[l-1]+3LL*MOD1)%MOD1*(inv1[l]%MOD1))%MOD1;
}
int sum2(int l,int r){
	if(l==0) return pref2[r]%MOD2;
	else 
		return ((pref2[r]-(ll)pref2[l-1]+3LL*MOD2)%MOD2*(inv2[l]%MOD2))%MOD2;
}

signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
string s;
cin>>s;
memset(pref1,0,sizeof(pref1));
if(n%2==0){
	cout<<"NOT POSSIBLE"<<endl;
	return 0;
}
inv1[0]=1;
inv1[1]=invmod(P,MOD1);
for(int i=2;i<MAXN;i++){
	inv1[i]=(inv1[i-1]%MOD1*(inv1[1]%MOD1))%MOD1;
}
int c=1;
for(int i=0;i<n;i++){
	int x=s[i]-'A'+1;
	if(i) pref1[i]=pref1[i-1];
	pref1[i]%=MOD1;
	pref1[i]+=(x%MOD1*c%MOD1)%MOD1;
	c=(c%MOD1*P%MOD1)%MOD1;
}
inv2[0]=1;
inv2[1]=invmod(P2,MOD2);
for(int i=2;i<MAXN;i++){
	inv2[i]=(inv2[i-1]%MOD2*(inv2[1]%MOD2))%MOD2;
}
c=1;
for(int i=0;i<n;i++){
	int x=s[i]-'A'+1;
	if(i) pref2[i]=pref2[i-1];
	pref2[i]+=(x%MOD2*c%MOD2)%MOD2;
	c=(c%MOD2*P2%MOD2)%MOD2;
}
vector<pair<int,int>> ans;
map<int,pair<int,int>> mp;
for(int i=0;i<n;i++){
	int l1=0,r1=0,l2=0,r2=n-1;
	if(i==0){
		l1=1;
	}
	if(i==n-1){
		r2=n-2;
	}
	r1=l1+(n-2)/2;
	if(i>0&&i<=r1) r1++;
	l2=r2-(n-2)/2;
	if(i!=n-1&&i>=l2) l2--;
	if((i>r1&&i<l2)||i==0||i==n-1){
		if(sum1(l1,r1)==sum1(l2,r2)&&sum2(l1,r1)==sum2(l2,r2)) {
			mp[sum1(l1,r1)]={l1,r1};
			ans.pb({l1,r1});
		}
		else continue;
	}
	if(i<=r1){
		int t=i-1;
		int t1=i+1;
		int s1=0;
		s1+=sum1(l1,t);
		s1%=MOD1;
		s1+=binpow(P,(i%((n-2)/2+1)),MOD1)*sum1(t1,r1);
		s1%=MOD1;
		s1+=MOD1;
		s1%=MOD1;
		int s2=0;
		s2+=sum2(l1,t);
		s2%=MOD2;
		s2+=binpow(P2,(i%((n-2)/2+1)),MOD2)*sum2(t1,r1);
		s2%=MOD2;
		s2+=MOD2;
		s2%=MOD2;
		if(s1==sum1(l2,r2)%MOD1&&s2==sum2(l2,r2)%MOD2){
			ans.pb({l2,r2});
			mp[s1]={l2,r2};
		}
	}else{
		int t=i-1;
		int t1=i+1;
		int s1=0;
		s1+=sum1(l2,t);
		s1%=MOD1;
		s1+=binpow(P,(i%((n-2)/2+1)),MOD1)*sum1(t1,r2);
		s1%=MOD1;
		s1+=MOD1;
		s1%=MOD1;
		int s2=0;
		s2+=sum2(l2,t);
		s2%=MOD2;
		s2+=binpow(P2,(i%((n-2)/2+1)),MOD2)*sum2(t1,r2);
		s2%=MOD2;
		s2+=MOD2;
		s2%=MOD2;
		// dbg(s2,sum2(l1,r1))
		if(s1==sum1(l1,r1)&&s2==sum2(l1,r1)%MOD2) {
			ans.pb({l1,r1});
			mp[s1]={l1,r1};
		}
	}
}
// dbg("done")
if(mp.size()==1){
	pair<int,int> anss=mp.begin()->second;
	cout<<s.substr(anss.F,anss.S-anss.F+1)<<endl;
}else{
	if(mp.empty()){
		cout<<"NOT POSSIBLE"<<endl;
		return 0;
	}
	cout<<"NOT UNIQUE"<<endl;
	return 0;
}

}

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