oj.uz

답안 #957528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957528 2024-04-04T01:18:41 Z YassirSalama 세 명의 친구들 (BOI14_friends) C++17
35 / 100
 12 ms 11008 KB 
#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 mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100,P=31;
int binpow(int a,int b){
	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){
	return binpow(a,mod-2)%mod;
}
int pref[MAXN];
int inv[MAXN];
int sum(int l,int r){
	if(l==0) return pref[r]%mod;
	else 
		return ((pref[r]-pref[l-1]+2*mod)%mod*(inv[l]%mod))%mod;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
string s;
cin>>s;
if(n%2==0){
	cout<<"NOT POSSIBLE"<<endl;
	return 0;
}
inv[0]=1;
inv[1]=invmod(P);
for(int i=2;i<MAXN;i++){
	inv[i]=(inv[i-1]%mod*(inv[1]%mod))%mod;
}
int c=1;
memset(pref,0,sizeof(pref));
for(int i=0;i<n;i++){
	int x=s[i]-'A'+1;
	if(i) pref[i]=pref[i-1];
	pref[i]%=mod;
	pref[i]+=(x%mod*c%mod)%mod;
	// dbg(x,c)
	c=(c%mod*P%mod)%mod;
}
map<int,pair<int,int>> mp;
vector<pair<int,int>> ans;
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(sum(l1,r1)==sum(l2,r2)) mp[sum(l1,r1)]={l1,r1};
		else continue;
	}
	if(i<=r1){
		int t=i-1;
		int t1=i+1;
		int s=0;
		s+=sum(l1,t);
		s%=mod;
		s+=binpow(P,(i%((n-2)/2+1)))*sum(t1,r1);
		s%=mod;
		s+=mod;
		s%=mod;
		if(s==sum(l2,r2)%mod) mp[s]={l2,r2};
	}else{
		int t=i-1;
		int t1=i+1;
		int s=0;
		s+=sum(l2,t);
		s%=mod;
		s+=binpow(P,(i%((n-2)/2+1)))*sum(t1,r2);
		s%=mod;
		s+=mod;
		s%=mod;
		if(s==sum(l1,r1)) mp[s]={l1,r1};
	}
}
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.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3572 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3416 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 2 ms 3416 KB Output is correct
10 Correct 2 ms 3416 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 2 ms 3420 KB Output is correct
15 Correct 2 ms 3420 KB Output is correct
16 Correct 2 ms 3420 KB Output is correct
17 Correct 2 ms 3416 KB Output is correct
18 Correct 2 ms 3420 KB Output is correct
19 Correct 2 ms 3416 KB Output is correct
20 Correct 2 ms 3544 KB Output is correct
21 Correct 2 ms 3420 KB Output is correct
22 Correct 2 ms 3420 KB Output is correct
23 Correct 2 ms 3420 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 2 ms 3420 KB Output is correct
28 Correct 2 ms 3420 KB Output is correct
29 Correct 2 ms 3420 KB Output is correct
30 Correct 2 ms 3420 KB Output is correct
31 Correct 2 ms 3420 KB Output is correct
32 Correct 2 ms 3420 KB Output is correct
33 Correct 2 ms 3420 KB Output is correct
34 Correct 2 ms 3420 KB Output is correct
35 Correct 2 ms 3420 KB Output is correct
36 Correct 2 ms 3416 KB Output is correct
37 Correct 2 ms 3420 KB Output is correct
38 Correct 2 ms 3420 KB Output is correct
39 Correct 2 ms 3420 KB Output is correct
40 Correct 2 ms 3420 KB Output is correct
41 Correct 2 ms 3416 KB Output is correct
42 Correct 2 ms 3420 KB Output is correct
43 Correct 2 ms 3420 KB Output is correct
44 Correct 2 ms 3420 KB Output is correct
45 Correct 2 ms 3420 KB Output is correct
46 Correct 2 ms 3416 KB Output is correct
47 Correct 2 ms 3420 KB Output is correct
48 Correct 2 ms 3664 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 2 ms 3416 KB Output is correct
51 Correct 2 ms 3420 KB Output is correct
52 Correct 2 ms 3452 KB Output is correct
53 Correct 2 ms 3420 KB Output is correct
54 Correct 2 ms 3416 KB Output is correct

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 11008 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -