oj.uz

답안 #762540

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
762540 2023-06-21T13:24:31 Z BidoTeima 세 명의 친구들 (BOI14_friends) C++17
0 / 100
 306 ms 52320 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1e9 + 9;
ll mul(ll a, ll b){
    return a % mod * (b % mod) % mod;
}
ll add(ll a, ll b){
    return (a + b) % mod;
}
ll sub(ll a, ll b){
    return (a + mod - b) % mod;
}
ll binexp(ll a, ll b){
    if(!b)
        return 1;
    ll ret = 1;
    while(b){
        if(b & 1)
            ret = mul(ret, a);
        b>>=1;
        a = mul(a, a);
    }
    return ret;
}
ll modinv(ll a){
    return binexp(a, mod - 2);
} 
#define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
#define combine(hash1, hash2, v) add(mul(hash2, v), hash1)
int main()
{ 
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    int n,cnt=0;
    string s;
    cin>>n>>s;
    if(n == 1 || n % 2 == 0){
        return cout<<"NOT POSSIBLE", 0;
    }
    ll p = 31, pw = 1;
    ll hash[n],inv[n],c[n];
    inv[0]=1;
    inv[1] = modinv(p);
    for(int i = 0; i < n; i++){
        c[i] = pw;
        hash[i] = mul(s[i] - 'A' + 1, pw);
        if(i)hash[i] = add(hash[i], hash[i - 1]);
        pw=mul(pw,p);
        if(i >= 2)inv[i]=mul(inv[1],inv[i-1]);
    }
    int l = -1, r = -1, rev = 0;
    for(int i = 0; i < n / 2; i++){
        ll val1,val2=val(hash, n / 2 + 1, n - 1);
        if(i == 0){
            val1 = val(hash, i + 1, n / 2);
        }else{
            val1 = combine(val(hash, 0, i - 1), val(hash, i + 1, n / 2), c[i]);
        } 
        if(val1==val2){
            l = n / 2 + 1, r = n - 1;
            ++cnt;
        }
    }  
    if(val(hash, 0, n / 2 - 1) == val(hash, n / 2 + 1, n - 1))++cnt, l = 0, r = n / 2 - 1;
    reverse(s.begin(), s.end());
    inv[0]=1;
    inv[1] = modinv(p);
    pw=1;
    for(int i = 0; i < n; i++){
        c[i] = pw;
        hash[i] = mul(s[i] - 'A' + 1, pw);
        if(i)hash[i] = add(hash[i], hash[i - 1]);
        pw=mul(pw,p);
        if(i >= 2)inv[i]=mul(inv[1],inv[i-1]);
    }
    for(int i = 0; i < n / 2; i++){
        ll val1,val2=val(hash, n / 2 + 1, n - 1);
        if(i == 0){
            val1 = val(hash, i + 1, n / 2);
        }else{
            val1 = combine(val(hash, 0, i - 1), val(hash, i + 1, n / 2), c[i]);
        } 
        if(val1==val2){
            l = n / 2 + 1, r = n - 1, rev = 1;
            ++cnt;
        }
    }  
    if(cnt == 0){
        cout<<"NOT POSSIBLE";
    }
    else if(cnt == 1){
        if(!rev){
            reverse(s.begin(),s.end());
            for(int i = l; i <= r; i++)cout<<s[i];
        }
        else{
            for(int i = r; i >= l; i--)cout<<s[i];
        }
    }
    else{
        cout<<"NOT UNIQUE";
    }
    return 0;
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
   29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
      |                                          ^
friends.cpp:53:22: note: in expansion of macro 'val'
   53 |         ll val1,val2=val(hash, n / 2 + 1, n - 1);
      |                      ^~~
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
   29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
      |                                          ^
friends.cpp:64:35: note: in expansion of macro 'val'
   64 |     if(val(hash, 0, n / 2 - 1) == val(hash, n / 2 + 1, n - 1))++cnt, l = 0, r = n / 2 - 1;
      |                                   ^~~
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
   29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
      |                                          ^
friends.cpp:77:22: note: in expansion of macro 'val'
   77 |         ll val1,val2=val(hash, n / 2 + 1, n - 1);
      |                      ^~~

Subtask #1
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 324 KB Output is correct
22 Correct 1 ms 320 KB Output is correct
23 Correct 1 ms 296 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 320 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 316 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 1 ms 316 KB Output is correct
39 Correct 1 ms 312 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 316 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Incorrect 1 ms 340 KB Output isn't correct
51 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 52264 KB Output is correct
2 Correct 306 ms 52320 KB Output is correct
3 Correct 304 ms 52216 KB Output is correct
4 Correct 305 ms 52208 KB Output is correct
5 Incorrect 288 ms 51292 KB Output isn't correct
6 Halted 0 ms 0 KB -