# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
180310 | rzbt | 세 명의 친구들 (BOI14_friends) | C++14 | 119 ms | 50496 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 2000006
typedef long long ll;
using namespace std;
const ll MOD = 1e9+9;
ll n;
char s[MAXN];
ll hes[MAXN];
ll stepen[MAXN];
ll res=0;
ll posl;
vector<ll> svi;
int main()
{
scanf("%lld", &n);
if(!(n&1)){
printf("NOT POSSIBLE");
return 0;
}
scanf("%s",s);
hes[0]=s[0]-'A'+1;
stepen[0]=1;
for(ll i=1;i<n;i++){
stepen[i]=(47*stepen[i-1])%MOD;
hes[i]=(stepen[i]*(s[i]-'A'+1)+hes[i-1])%MOD;
}
for(ll i=0;i<n;i++){
if(i<(n>>1)){
ll th=hes[n>>1]-hes[i];
if(i!=0)th+=hes[i-1]*stepen[1];
th=(MOD+MOD+MOD+th)%MOD;
th*=stepen[n/2];
th%=MOD;
if(th==(MOD+hes[n-1]-hes[n>>1])%MOD){
res++,posl=i;
svi.pb(th);
}
}
if(i>(n>>1)){
ll th=hes[n-1]-hes[i];
th+=(hes[i-1]-hes[(n>>1)-1])*stepen[1];
th=(MOD+MOD+MOD+th)%MOD;
//printf(" %lld %lld\n",th,(hes[(n>>1)-1]*stepen[(n>>1)+1])%MOD );
if(th==(hes[(n>>1)-1]*stepen[(n>>1)+1])%MOD ){
res++,posl=i;
svi.pb(th);
}
}
if(i==(n>>1)){
ll ta=hes[(n>>1)-1];
ll tb=(MOD+hes[n-1]-hes[(n>>1)])%MOD;
//printf("%lld %lld %lld %lld",ta,tb,stepen[(n>>1)+1],(ta*stepen[(n>>1)+1])%MOD);
if(tb==(ta*stepen[(n>>1)+1])%MOD){
res++,posl=i;
svi.pb(tb);
}
}
}
if(res==0)printf("NOT POSSIBLE");
else{
for(int i=0;i<svi.size()-1;i++){
if(svi[i]!=svi[i+1]){
printf("NOT UNIQUE");
return 0;
}
}
ll gran=(n>>1);
for(ll i=0;i<gran;i++){
if(i==posl)gran++;
else putchar(s[i]);
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |