oj.uz

답안 #851142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851142 2023-09-18T15:40:09 Z emkow 세 명의 친구들 (BOI14_friends) C++17
100 / 100
 98 ms 45800 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define pb emplace_back
#define ins insert
#define ssize(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pld pair <ld, ld>
#define st first
#define nd second

using namespace std;
using ll = int_fast64_t;
// using lll = __int128_t;
using ld = long double;
const int oo = 1e9 + 7;
const int mod = 1e9 + 9;

struct Hash{
    int n, p = 2137;
    vector <ll> h, pw;
    Hash(string &s){
        n = s.length();
        pw.resize(n + 1);
        pw[0] = 1;
        for(int i = 1; i <= n; i ++){
            pw[i] = pw[i - 1] * p;
            if(pw[i] >= mod) pw[i] %= mod;
        }
        h.resize(n + 1);
        for(int i = 1; i <= n; i ++){
            ll x = (pw[i] * (ll)(s[i - 1] - 'A' + 1));
            if(x >= mod) x %= mod;
            h[i] = h[i - 1] + x;
            if(h[i] >= mod) h[i] %= mod;
        }
    }
    ll get(int a, int b){
        ll r = (h[b] - h[a - 1] + mod) % mod;
        r = (r * pw[n - a]);
        if(r >= mod) r %= mod;
        return r;
    }
    ll gett(int a, int b, int c, int d){
        ll h1 = get(a, b), h2 = get(c, d);
        h2 = (h2 * pw[b - a + 1]);
        if(h2 >= mod) h2 %= mod;
        ll r = (h1 + h2);
        if(r >= mod) r %= mod;
        return r;
    }
};

void solve(){
    int n; cin >> n;
    string s; cin >> s;
    if(!(n & 1)){
        cout << "NOT POSSIBLE\n";
        return;
    }
    Hash H(s);
    vector <int> ev;
    int k = (n + 1) / 2, l = n / 2;
    if(H.get(2, 2 + l - 1) == H.get(n - l + 1, n)) ev.pb(1);
    for(int i = 2; i < n; i ++){
        if(i == k){
            if(H.get(1, k - 1) == H.get(k + 1, n)) ev.pb(i);
        }
        if(i < k){
            if(H.get(n - l + 1, n) == H.gett(1, i - 1, i + 1, k)) ev.pb(i);
        }
        if(i > k){
            if(H.get(1, l) == H.gett(k, i - 1, i + 1, n)) ev.pb(i);
        }
    }
    if(H.get(1, 1 + l - 1) == H.get(n - l, n - 1)) ev.pb(n);
    if(!ssize(ev)){
        cout << "NOT POSSIBLE\n";
        return;
    }
    int idx = ev[0];
    if(ssize(ev) > 1){
        ll hsh = 0;
        bool ok = 1;
        if(idx < k){
            hsh = H.get(k + 1, n);
            for(int i = 1; i < ssize(ev); i ++){
                if(ev[i] < k) continue;
                if(hsh != H.get(1, l)) ok = 0;
            }
            if(!ok){
                cout << "NOT UNIQUE\n";
                return;
            }
        }
    }
    if(idx >= k){
        for(int i = 1; i <= l; i ++) cout << s[i - 1];
    }
    else{
        for(int i = n - l + 1; i <= n; i ++) cout << s[i - 1];
    }
    cout << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; t = 1;
    // cin >> t;
    while(t --) solve();
    return 0;
}

Subtask #1
35.0 / 35.0

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

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 34832 KB Output is correct
2 Correct 93 ms 36624 KB Output is correct
3 Correct 93 ms 36596 KB Output is correct
4 Correct 92 ms 36656 KB Output is correct
5 Correct 92 ms 36592 KB Output is correct
6 Correct 4 ms 4348 KB Output is correct
7 Correct 98 ms 45800 KB Output is correct
8 Correct 69 ms 32240 KB Output is correct
9 Correct 86 ms 33008 KB Output is correct
10 Correct 84 ms 33316 KB Output is correct
11 Correct 54 ms 29952 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 1 ms 344 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Correct 1 ms 600 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 344 KB Output is correct
44 Correct 0 ms 344 KB Output is correct
45 Correct 0 ms 344 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 1 ms 344 KB Output is correct
51 Correct 0 ms 344 KB Output is correct
52 Correct 0 ms 344 KB Output is correct
53 Correct 1 ms 344 KB Output is correct
54 Correct 0 ms 452 KB Output is correct