제출 #492985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492985		MilosMilutinovic	세 명의 친구들 (BOI14_friends)	C++14	0 / 100	87 ms	34500 KiB

friends

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=2000005;
const int p=13831;
int n;
char s[N];
ll pw[N],hsh[N];
ll get(int l,int r) {
    ll pp=hsh[r]-(hsh[l-1]*pw[r-l+1]%mod);
    if (pp<0) pp+=mod;
    return pp;
}
bool check(int l1,int r1,int l2,int r2) {
    return get(l1,r1)==get(l2,r2);
}
int main() {
    scanf("%d",&n);
    scanf("%s",s+1);
    hsh[0]=0;
    pw[0]=1;
    rep(i,1,n+1) {
        pw[i]=(pw[i-1]*p)%mod;
        hsh[i]=((hsh[i-1]*p)+s[i])%mod;
    }
    if (n%2==0) {
        puts("NOT POSSIBLE");
        return 0;
    }
    VI ans;
    rep(i,1,n+1) {
        if (i==n/2+1) {
            if (check(1,i-1,i+1,n)) ans.pb(i);
        } else if (i<=n/2) {
            if (i==1) {
                if (check(i+1,i+n/2,i+n/2+1,n)) ans.pb(i);
            } else {
                if (check(1,i-1,n/2+2,n/2+i)&&check(i+1,n/2+1,n/2+i+1,n)) ans.pb(i);
            }
        } else {
            if (i==n) {
                if (check(1,n/2,n/2+1,n-1)) ans.pb(i);
            } else {
                if (check(1,i-(n/2+1),n/2+1,i-1)&&check(i-(n/2+1)+1,n/2,i+1,n)) ans.pb(i);
            }
        }
    }
    if (ans.empty()) {
        puts("NOT POSSIBLE");
        return 0;
    }
    if (SZ(ans)>1) {
        puts("NOT UNIQUE");
        return 0;
    }
    rep(i,1,n/2+1+(ans[0]<=n/2)) {
        if (i==ans[0]) continue;
        printf("%c",s[i]);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

friends.cpp: In function 'int main()':
friends.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
friends.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%s",s+1);
      |     ~~~~~^~~~~~~~~~

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