Submission #492991

#	Time	Username	Problem	Language	Result	Execution time	Memory
492991		MilosMilutinovic	Three Friends (BOI14_friends)	C++14	100 / 100	146 ms	73884 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 mod1=998244353;
const ll mod2=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 p1=777777;
const int p2=9973;
int n;
char s[N];
ll pw1[N],hsh1[N];
ll pw2[N],hsh2[N];
ll get1(int l,int r) {
    ll pp=hsh1[r]-(hsh1[l-1]*pw1[r-l+1]%mod1);
    if (pp<0) pp+=mod1;
    return pp;
}
ll get2(int l,int r) {
    ll pp=hsh2[r]-(hsh2[l-1]*pw2[r-l+1]%mod2);
    if (pp<0) pp+=mod2;
    return pp;
}
bool check(int l1,int r1,int l2,int r2) {
    return get1(l1,r1)==get1(l2,r2)&&get2(l1,r1)==get2(l2,r2);
}
int main() {
    scanf("%d",&n);
    scanf("%s",s+1);
    hsh1[0]=0;
    pw1[0]=1;
    rep(i,1,n+1) {
        pw1[i]=(pw1[i-1]*p1)%mod1;
        hsh1[i]=((hsh1[i-1]*p1)+s[i])%mod1;
    }
    hsh2[0]=0;
    pw2[0]=1;
    rep(i,1,n+1) {
        pw2[i]=(pw2[i-1]*p2)%mod2;
        hsh2[i]=((hsh2[i-1]*p2)+s[i])%mod2;
    }
    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);
            }
        }
    }
    map<int,int> mapcina;
    rep(i,0,SZ(ans)) {
        if (ans[i]<=n/2) mapcina[get1(n-n/2+1,n)]++;
        else mapcina[get1(1,n/2)]++;
    }
    if (SZ(mapcina)>1) {
        puts("NOT UNIQUE");
        return 0;
    }
    if (ans.empty()) {
        puts("NOT POSSIBLE");
        return 0;
    }
    rep(i,1,n/2+1+(ans[0]<=n/2)) {
        if (i==ans[0]) continue;
        printf("%c",s[i]);
    }
}

Compilation message (stderr)

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

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