oj.uz

답안 #379570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379570 2021-03-18T16:06:58 Z Kubin 세 명의 친구들 (BOI14_friends) C++17
100 / 100
 103 ms 39652 KB 
#include <bits/stdc++.h>

using namespace std;

vector<size_t> prefixoprefixes(string S)
{
    const size_t n = S.size();
    vector<size_t> Z(n);
    for(size_t i = 1, p = 0; i < n; i++)
    {
        if(i <= p + Z[p])
            Z[i] = min(Z[i - p], p + Z[p] - i);
        while(i + Z[i] < n and S[Z[i]] == S[i+Z[i]])
            Z[i]++;
        if(i + Z[i] > p + Z[p])
            p = i;
    }
    return Z;
}

bool square_insert(string S)
{
    auto P = prefixoprefixes(S);
    auto Q = prefixoprefixes(string(S.rbegin(), S.rend()));
    reverse(Q.begin(), Q.end());
    const size_t n = S.size() / 2;
    for(size_t i = 0; i <= n; i++)
        if(P[n+1] >= i and Q[n] >= n - i)
            return true;
    return false;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);

    size_t n;
    cin >> n;

    string S;
    cin >> S;

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

    auto l = square_insert(S), r = square_insert(string(S.rbegin(), S.rend()));
    auto L = S.substr(S.size()/2 + 1, S.size()/2), R = S.substr(0, S.size()/2);

    if(l and r and L != R)
        cout << "NOT UNIQUE" << endl;
    else if(l)
        cout << L << endl;
    else if(r)
        cout << R << endl;
    else
        cout << "NOT POSSIBLE" << endl;
}

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

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