oj.uz

답안 #309685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
309685 2020-10-04T09:22:09 Z nicolaalexandra 세 명의 친구들 (BOI14_friends) C++14
100 / 100
 264 ms 66424 KB 
#include <bits/stdc++.h>
#define DIM 2000010
#define MOD1 1000000007
#define MOD2 1000000009
using namespace std;

long long hash1[DIM],hash2[DIM],p1[DIM],p2[DIM];
map <pair<long long,long long>, int> f;
char s[DIM];
int n,i;

pair <long long,long long> get_hash (int x, int y){

    if (x > y)
        return make_pair (0,0);

    long long val1 = (hash1[y] - hash1[x-1] * p1[y-x+1] % MOD1 + MOD1) % MOD1;
    long long val2 = (hash2[y] - hash2[x-1] * p2[y-x+1] % MOD2 + MOD2) % MOD2;

    return make_pair (val1,val2);

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>s+1;

    if (n % 2 == 0){
        cout<<"NOT POSSIBLE";
        return 0;
    }

    for (i=1;i<=n;i++){
        hash1[i] = (hash1[i-1] * 30 + s[i] - 'A' + 1) % MOD1;
        hash2[i] = (hash2[i-1] * 30 + s[i] - 'A' + 1) % MOD2;
    }

    p1[0] = p2[0] = 1;
    for (i=1;i<=n;i++){
        p1[i] = 1LL * p1[i-1] * 30 % MOD1;
        p2[i] = 1LL * p2[i-1] * 30 % MOD2;
    }

    int lg = (n-1) / 2, sol = 0, poz = 0;

    for (i=1;i<=n;i++){
        if (i <= lg){

            pair <long long,long long> cod1 = get_hash (i+1,lg+1);
            long long val1 = (hash1[i-1] * p1[lg+1-i] % MOD1 + cod1.first) % MOD1;
            long long val2 = (hash2[i-1] * p2[lg+1-i] % MOD2 + cod1.second) % MOD2;

            pair <long long,long long> cod2 = get_hash (lg+2,n);

            if (val1 == cod2.first && val2 == cod2.second){
                if (!f[make_pair(val1,val2)])
                    sol++;
                f[make_pair(val1,val2)]++;
                poz = i;
            }


        } else {

            /// lg+1...i-1 + i+1...n
            pair <long long,long long> cod1 = get_hash (lg+1,i-1);
            pair <long long,long long> cod2 = get_hash (i+1,n);

            long long val1 = (cod1.first * p1[n-i] % MOD1 + cod2.first) % MOD1;
            long long val2 = (cod1.second * p2[n-i] % MOD2 + cod2.second) % MOD2;

            if (val1 == hash1[lg] && val2 == hash2[lg]){
                if (!f[make_pair(val1,val2)])
                    sol++;
                f[make_pair(val1,val2)]++;
                poz = i;
            }
        }
    }

    if (!sol){
        cout<<"NOT POSSIBLE";
        return 0;
    }

    if (sol > 1){
        cout<<"NOT UNIQUE";
        return 0;
    }

    for (i=1;i<=lg;i++){
        if (i == poz){
            lg++;
            continue;
        }
        cout<<s[i];
    }


    return 0;
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     cin>>n>>s+1;
      |             ~^~

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 65912 KB Output is correct
2 Correct 240 ms 65920 KB Output is correct
3 Correct 240 ms 65912 KB Output is correct
4 Correct 236 ms 65912 KB Output is correct
5 Correct 244 ms 66040 KB Output is correct
6 Correct 88 ms 2808 KB Output is correct
7 Correct 264 ms 66424 KB Output is correct
8 Correct 180 ms 60280 KB Output is correct
9 Correct 216 ms 61176 KB Output is correct
10 Correct 213 ms 61176 KB Output is correct
11 Correct 168 ms 55800 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 0 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 0 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 0 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 0 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 0 ms 384 KB Output is correct
38 Correct 0 ms 384 KB Output is correct
39 Correct 1 ms 384 KB Output is correct
40 Correct 0 ms 384 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 1 ms 384 KB Output is correct
43 Correct 0 ms 384 KB Output is correct
44 Correct 0 ms 384 KB Output is correct
45 Correct 1 ms 384 KB Output is correct
46 Correct 1 ms 384 KB Output is correct
47 Correct 1 ms 384 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 1 ms 384 KB Output is correct
50 Correct 1 ms 384 KB Output is correct
51 Correct 0 ms 384 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 1 ms 384 KB Output is correct
54 Correct 1 ms 384 KB Output is correct