oj.uz

Submission #492991

# Submission time Handle Problem Language Result Execution time Memory
492991 2021-12-09T22:54:01 Z MilosMilutinovic Three Friends (BOI14_friends) C++14
100 / 100
 146 ms 73884 KB 
#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

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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 284 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 352 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 0 ms 296 KB Output is correct
24 Correct 0 ms 332 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 0 ms 332 KB Output is correct
27 Correct 0 ms 332 KB Output is correct
28 Correct 0 ms 332 KB Output is correct
29 Correct 0 ms 332 KB Output is correct
30 Correct 0 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 0 ms 332 KB Output is correct
33 Correct 0 ms 332 KB Output is correct
34 Correct 0 ms 332 KB Output is correct
35 Correct 0 ms 332 KB Output is correct
36 Correct 0 ms 332 KB Output is correct
37 Correct 0 ms 332 KB Output is correct
38 Correct 0 ms 332 KB Output is correct
39 Correct 0 ms 332 KB Output is correct
40 Correct 0 ms 332 KB Output is correct
41 Correct 0 ms 332 KB Output is correct
42 Correct 0 ms 332 KB Output is correct
43 Correct 0 ms 332 KB Output is correct
44 Correct 1 ms 332 KB Output is correct
45 Correct 1 ms 332 KB Output is correct
46 Correct 0 ms 332 KB Output is correct
47 Correct 1 ms 332 KB Output is correct
48 Correct 1 ms 332 KB Output is correct
49 Correct 0 ms 332 KB Output is correct
50 Correct 1 ms 332 KB Output is correct
51 Correct 0 ms 336 KB Output is correct
52 Correct 1 ms 336 KB Output is correct
53 Correct 0 ms 336 KB Output is correct
54 Correct 0 ms 336 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 65760 KB Output is correct
2 Correct 102 ms 65764 KB Output is correct
3 Correct 102 ms 65856 KB Output is correct
4 Correct 105 ms 65764 KB Output is correct
5 Correct 109 ms 65844 KB Output is correct
6 Correct 49 ms 64832 KB Output is correct
7 Correct 146 ms 73884 KB Output is correct
8 Correct 68 ms 58488 KB Output is correct
9 Correct 103 ms 61000 KB Output is correct
10 Correct 96 ms 61128 KB Output is correct
11 Correct 54 ms 55768 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 0 ms 312 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Correct 0 ms 336 KB Output is correct
22 Correct 0 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 0 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 0 ms 336 KB Output is correct
28 Correct 0 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 0 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 0 ms 336 KB Output is correct
33 Correct 0 ms 336 KB Output is correct
34 Correct 0 ms 336 KB Output is correct
35 Correct 0 ms 308 KB Output is correct
36 Correct 0 ms 336 KB Output is correct
37 Correct 0 ms 336 KB Output is correct
38 Correct 0 ms 336 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 0 ms 336 KB Output is correct
41 Correct 0 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 0 ms 336 KB Output is correct
44 Correct 1 ms 336 KB Output is correct
45 Correct 0 ms 336 KB Output is correct
46 Correct 0 ms 336 KB Output is correct
47 Correct 0 ms 336 KB Output is correct
48 Correct 0 ms 336 KB Output is correct
49 Correct 0 ms 336 KB Output is correct
50 Correct 0 ms 336 KB Output is correct
51 Correct 0 ms 336 KB Output is correct
52 Correct 0 ms 336 KB Output is correct
53 Correct 0 ms 336 KB Output is correct
54 Correct 0 ms 336 KB Output is correct