Submission #549885

#	Time	Username	Problem	Language	Result	Execution time	Memory
549885		Pherokung	Three Friends (BOI14_friends)	C++14	100 / 100	126 ms	52172 KiB

friends

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7, p = 101;
ll n,pw[2000005],ans=-1,l[2000005],r[2000005],val;
map<ll,ll> mp;
char s[2000005];
ll mul(ll a,ll b) {return (a*b) % mod;}
ll add(ll a,ll b) {return (a+b) % mod;}
ll sub(ll a,ll b) {return (a-b+mod) % mod;}

int main(){
	scanf("%lld%s",&n,s+1);
	if(!(n%2)){
		printf("NOT POSSIBLE");
		return 0;
	}
	pw[0] = 1; 
	for(int i=1;i<=n;i++) pw[i] = mul(pw[i-1],p);
	val = 0;
	for(int i=1;i<=n;i++){
		val = mul(val,p), val = add(val,(s[i]-'A'+1));
		l[i] = val;
	}
	val = 0;
	for(int i=n;i>=1;i--){
		val = add(val,mul((s[i]-'A'+1),pw[n-i]));
		r[i] = val;
	}
	
	for(int i=1;i<=n;i++){
		ll L = n/2, R = n/2+2, M = n/2+1;
		if(i <= L){
			val = sub(l[M],mul(l[i],pw[M-i]));
			val = add(mul(l[i-1],pw[M-i]),val);
			if(val == r[R]){
				if(ans == -1 || mp[val] == 1) ans = i;
				else{
					printf("NOT UNIQUE");
					return 0;
				}
				mp[val] = 1;
			}
		}
		else if(i == M){
			if(l[L] == r[R]){
				if(ans == -1 || mp[l[L]] == 1) ans = i;
				else{
					printf("NOT UNIQUE",ans,i);
					return 0;
				}
				mp[l[L]] = 1;
			}
		}
		else if(i >= R){
			val = sub(l[i-1],mul(l[M-1],pw[i-M]));
			ll xxx = val;
			val = add(mul(val,pw[n-i]),r[i+1]);
			if(l[L] == val){
				if(ans == -1 || mp[val] == 1) ans = i;
				else{
					printf("NOT UNIQUE",ans,i);
					return 0;
				}
				mp[val] = 1;
			}
		}
	}
	if(ans == -1) printf("NOT POSSIBLE");
	else{
		ll cnt = n/2, pos = 1;
		while(cnt){
			if(pos != ans){
				printf("%c",s[pos]);
				cnt--;
			}
			pos++;
		}
	}
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:49:13: warning: too many arguments for format [-Wformat-extra-args]
   49 |      printf("NOT UNIQUE",ans,i);
      |             ^~~~~~~~~~~~
friends.cpp:62:13: warning: too many arguments for format [-Wformat-extra-args]
   62 |      printf("NOT UNIQUE",ans,i);
      |             ^~~~~~~~~~~~
friends.cpp:57:7: warning: unused variable 'xxx' [-Wunused-variable]
   57 |    ll xxx = val;
      |       ^~~
friends.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%lld%s",&n,s+1);
      |  ~~~~~^~~~~~~~~~~~~~~~~

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