oj.uz

Submission #648361

# Submission time Handle Problem Language Result Execution time Memory
648361 2022-10-06T08:47:30 Z Ronin13 Three Friends (BOI14_friends) C++14
100 / 100
 148 ms 40688 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int NMAX = 2e6 + 1;
const ll mod = 1e9 + 7;
ll p[NMAX];
ll h[NMAX];
const ll pr = 31;

void hashing(string &s){
    h[0] = s[0] - 'A' + 1;
    for(int i = 1; i < s.size(); i++){
        int x = s[i] - 'A' + 1;
        h[i] = h[i - 1] * pr + (ll)x;
        h[i] %= mod;
    }
}

ll get(int l, int r){
    if(l == 0) return h[r];
    ll x = h[r];
    ll y = h[l - 1]; y *= p[r - l + 1]; y %= mod;
    x -= y; x %= mod; x += mod; x %= mod;
    return x % mod;
}

int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        if(i)
            p[i] = p[i - 1] * pr % mod;
        else p[i] = 1;
        //cout << p[i] << ' ';
    }
    string s; cin >> s;
    hashing(s);


    int ans = -1;
    int anshash = -1;
    if(n % 2 == 0){
        cout << "NOT POSSIBLE";
        return 0;
    }
   // cout << get(4, 6);
    int len = n / 2;
    for(int j = 0; j < n; j++){
        bool ind = false;
        ll curhash = 0;
        if(j < n / 2){
            ll x = 0, y = 0;
            if(j)
                x = get(0, j - 1);
            y = get(j + 1, n / 2);
            x *= p[n / 2 - j]; x %= mod;
            x += y;
            x %= mod;
            ll z = get(n / 2 + 1, n - 1);
            if(x == z) ind = true, curhash = z;
        }
        if(j == n / 2){
            ll x = get(0, n / 2 - 1);
            ll z = get(n / 2 + 1, n - 1);
            if(x == z) ind = true, curhash = z;
        }
        if(j > n / 2){
            ll x = get(n / 2, j - 1);
            ll y = 0;
            if(j < n - 1) y = get(j + 1, n - 1);
            x *= p[n - j - 1];
            x %= mod; x += y;
            x %= mod;
            ll z = get(0, n / 2 - 1);
            if(x == z) ind = true, curhash = z;
        }
        if(ind){
            if(ans != -1 && anshash != curhash){
                cout << "NOT UNIQUE";
                return 0;
            }
            ans = j;
            anshash = curhash;
        }
    }
    if(ans == -1){
        cout << "NOT POSSIBLE";
        return 0;
    }
    string res = "";
    for(int i = 0; i < n; i++){
        if(i == ans) continue;
        res += s[i];
    }
    for(int i = 0; i < res.size() / 2; i++){
        cout << res[i];
    }
    return 0;
}

Compilation message

friends.cpp: In function 'void hashing(std::string&)':
friends.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 1; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < res.size() / 2; i++){
      |                    ~~^~~~~~~~~~~~~~~~
friends.cpp:54:9: warning: unused variable 'len' [-Wunused-variable]
   54 |     int len = n / 2;
      |         ^~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 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 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 312 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 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 0 ms 340 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 1 ms 352 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 0 ms 340 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 1 ms 304 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 1 ms 308 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 39308 KB Output is correct
2 Correct 147 ms 39316 KB Output is correct
3 Correct 147 ms 39220 KB Output is correct
4 Correct 146 ms 39324 KB Output is correct
5 Correct 145 ms 39280 KB Output is correct
6 Correct 80 ms 35092 KB Output is correct
7 Correct 146 ms 40688 KB Output is correct
8 Correct 97 ms 31920 KB Output is correct
9 Correct 133 ms 34444 KB Output is correct
10 Correct 133 ms 34480 KB Output is correct
11 Correct 88 ms 29464 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 312 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 312 KB Output is correct
26 Correct 1 ms 308 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 308 KB Output is correct
32 Correct 0 ms 308 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 308 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 304 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 1 ms 308 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 308 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct