oj.uz

답안 #140024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140024 2019-08-01T22:12:27 Z silxikys 세 명의 친구들 (BOI14_friends) C++14
100 / 100
 165 ms 37696 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e6+6;
const int M = 1e9+7;
const int base = 31;
int mult(int a, int b) {
    return (1LL*a*b) % M;
}
int madd(int a, int b) {
    return (a+b) % M;
}
int modexp(int a, int b) {
    int res = 1;
    while (b) {
        if (b&1) res = mult(res,a);
        a = mult(a,a);
        b >>= 1;
    }
    return res;
}
int ctoi(char c) {
    return c-'A'+1;
}

int N;
string U;

int pwr[maxn], ipwr[maxn];
int pre[maxn];

int sub(int l, int r) {
    return mult((pre[r]-pre[l-1]+M)%M,ipwr[l-1]);
}

int comb(int l1, int r1, int l2, int r2) {
    int h1 = sub(l1,r1);
    int h2 = sub(l2,r2);
    int shift = r1-l1+1;
    return madd(h1,mult(h2,pwr[shift]));
}

map<int,pair<int,int>> ans;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> U;
    if (N % 2 == 0) {
        cout << "NOT POSSIBLE\n";        
        return 0;
    }
    pwr[0] = ipwr[0] = 1;
    for (int i = 1; i <= N; i++) {
        pwr[i] = mult(pwr[i-1],base);
    }
    ipwr[1] = modexp(base,M-2);
    for (int i = 2; i <= N; i++) {
        ipwr[i] = mult(ipwr[i-1],ipwr[1]);
    }
    for (int i = 1; i <= N; i++) {
        pre[i] = madd(pre[i-1],mult(ctoi(U[i-1]),pwr[i-1]));
    }
    vector<int> hashes; //hashes of the answers
    int mid = N/2+1;
    for (int i = 1; i <= N; i++) {
        int h1, h2;
        if (i <= mid) {
            h2 = sub(mid+1,N);
            if (i == 1) {
                h1 = sub(2,mid);
            }
            else if (i == mid) {
                h1 = sub(1,mid-1);
            }
            else {
                h1 = comb(1,i-1,i+1,mid);
            }
        }
        else {
            h1 = sub(1,mid-1);
            if (i == N) {
                h2 = sub(mid,N-1);
            }
            else {
                h2 = comb(mid,i-1,i+1,N);
            }
        }
        //cout << i << ": " << h1 << ' ' << h2 << '\n';
        if (h1 == h2) {
            hashes.push_back(h1);
            ans[h1] = (i <= mid) ? make_pair(mid+1,N) : make_pair(1,mid-1);
        }
        if (ans.size() > 1) {
            cout << "NOT UNIQUE\n";
            return 0;
        }
    }
    if (hashes.empty()) {
        cout << "NOT POSSIBLE\n";
    }
    else {
        int l = ans[hashes[0]].first;
        int r = ans[hashes[0]].second;
        for (int i = l; i <= r; i++) {
            cout << U[i-1];
        }
        cout << '\n';
    }
}

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 26892 KB Output is correct
2 Correct 141 ms 28996 KB Output is correct
3 Correct 140 ms 28956 KB Output is correct
4 Correct 140 ms 28828 KB Output is correct
5 Correct 140 ms 28804 KB Output is correct
6 Correct 9 ms 4376 KB Output is correct
7 Correct 165 ms 37696 KB Output is correct
8 Correct 103 ms 25240 KB Output is correct
9 Correct 126 ms 26012 KB Output is correct
10 Correct 126 ms 26088 KB Output is correct
11 Correct 101 ms 23196 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 504 KB Output is correct
34 Correct 2 ms 380 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 376 KB Output is correct
45 Correct 2 ms 376 KB Output is correct
46 Correct 2 ms 376 KB Output is correct
47 Correct 2 ms 376 KB Output is correct
48 Correct 2 ms 376 KB Output is correct
49 Correct 2 ms 376 KB Output is correct
50 Correct 2 ms 376 KB Output is correct
51 Correct 2 ms 376 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 2 ms 376 KB Output is correct
54 Correct 2 ms 376 KB Output is correct