oj.uz

Submission #879992

# Submission time Handle Problem Language Result Execution time Memory
879992 2023-11-28T14:15:37 Z Karoot Three Friends (BOI14_friends) C++17
100 / 100
 40 ms 44084 KB 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <deque>
 
#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()
 
using namespace std;
 
typedef long long ll;
 
ll linf = 1e15+1;
 
inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
const int MAXN = 2e6+1;
bool mem[MAXN][2];
int pref[MAXN][2];
int parent[MAXN];
int sill[MAXN];
int n;
 
bool foundFromRight;
 
int whatLetter[MAXN][30];
int letterPref[MAXN][30];
 
int rootOf(int x){
    return (parent[x] == x ? x : parent[x] = rootOf(parent[x]));
}
 
void merge(int a, int b){
    a = rootOf(a);
    b = rootOf(b);
    if (sill[a] < sill[b])swap(a, b);
    parent[b] = a;
    sill[a] += sill[b];
}
 
 
int main(){
    scoobydoobydoo();
    cin >> n;
    string s; cin >> s;
    if (n%2 == 0){
        cout << "NOT POSSIBLE" << endl;
        return 0;
    }
 
    int currentChecking = 0;
 
    sill[0] = 1;
    parent[0] = 0;
 
    for (int x = 1; x < n; x++){
        parent[x] = x;
        sill[x] = 1;
        if (s[x-1] == s[x]){
            merge(currentChecking, x);
        } else {
            currentChecking = x;
        }
    }   
 
 
    int jS = (n-1)/2;
    for (int i = 0; i <= n/2; i++){
        if (i + jS > n)break;
 
        if (s[i+jS] == s[i]){
            mem[i][0] = true;
        }
        if (s[i+jS+1] == s[i]){
            mem[i][1] = true;
        }
    }
 
    pref[0][0] = mem[0][0];
    pref[0][1] = mem[0][1];
 
 
    for (int i = 1; i < n; i++){
        pref[i][0] = pref[i-1][0] + mem[i][0];
        pref[i][1] = pref[i-1][1] + mem[i][1];
    }
    /*
    for (int i = 0; i < n; i++){
        cout << "(" << pref[i][0] << " " << pref[i][1] << ")  ";
    }
    cout << endl;
    */
    int works = -1;
    
 
    for (int i = 0; i <= n/2; i++){
        //is this One
        //HÖGRA + VÄNSTRA MÅSTE VARA LIKA MED jS
 
 
        int leftJ = (i == 0 ? 0 : pref[i-1][1]);
        int rightJ = pref[n/2][0]-pref[i][0];
        if (leftJ+rightJ == jS){
            if (works != -1 && rootOf(works) != rootOf(i)){
                cout << "NOT UNIQUE" << endl;
                return 0;
            } else {
                foundFromRight = false;
                works = i;
            }
        }
    }
 
 
 
    for (int i = 0; i < n; i++){
        pref[i][0] = 0;
        pref[i][1] = 0;
        mem[i][0] = false;
        mem[i][1] = false;
    }
 
    for (int i = n/2; i < n; i++){
        if (s[i-jS] == s[i]){
            mem[i][0] = true;
        }
        if (s[i-jS-1] == s[i]){
            mem[i][1] = true;
        }
    }
 
    pref[n-1][0] = mem[n-1][0];
    pref[n-1][1] = mem[n-1][1];
 
 
    for (int i = n-2; i >= 0; i--){
        pref[i][0] = pref[i+1][0] + mem[i][0];
        pref[i][1] = pref[i+1][1] + mem[i][1];
    }
    /*
    for (int i = 0; i < n; i++){
        cout << "(" << pref[i][0] << " " << pref[i][1] << ")  ";
    }
    cout << endl;
    */
 
    for (int i = n-1; i >= n/2; i--){
        //is this One
        //DE TILL HÖGER MÅSTE HOPPA LÄNGRE, TILL VÄNSTER EJ
        //HÖGER BORDE HA EN HOPP-PREFIX
        int rightJ = (i == n-1 ? 0 : pref[i+1][1]);
        int leftJ = pref[n/2][0]-pref[i][0];
        if (leftJ+rightJ == jS){
            if (works != -1 && works != i && rootOf(works) != rootOf(i)){
                //cout << i << endl;
                cout << "NOT UNIQUE" << endl;
                return 0;
            } else {
                foundFromRight = true;
                works = i;
            }
        }
    }
 
    
 
 
    if (works == -1){
        cout << "NOT POSSIBLE" << endl;
        return 0;
    }
    string ans = "";
 
    if (foundFromRight){
        for (int i = n/2; i < works; i++){
            ans += s[i];
        }
        for (int i = works+1; i < n; i++){
            ans += s[i];
        }
        cout << ans << endl;
        return 0;
    }
 
    for (int i = 0; i < works; i++){
        ans += s[i];
    }
    for (int i = works+1; i <= n/2; i++){
        ans += s[i];
    }
 
 
    cout << ans << endl;
 
 
 
 
 
    return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8652 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 2 ms 8536 KB Output is correct
13 Correct 1 ms 8536 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8660 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 0 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 0 ms 2396 KB Output is correct
27 Correct 2 ms 8540 KB Output is correct
28 Correct 2 ms 8552 KB Output is correct
29 Correct 1 ms 8536 KB Output is correct
30 Correct 1 ms 8656 KB Output is correct
31 Correct 1 ms 8652 KB Output is correct
32 Correct 1 ms 8540 KB Output is correct
33 Correct 1 ms 8540 KB Output is correct
34 Correct 1 ms 8540 KB Output is correct
35 Correct 1 ms 8540 KB Output is correct
36 Correct 1 ms 8540 KB Output is correct
37 Correct 1 ms 8536 KB Output is correct
38 Correct 1 ms 8536 KB Output is correct
39 Correct 1 ms 8540 KB Output is correct
40 Correct 1 ms 8656 KB Output is correct
41 Correct 1 ms 8652 KB Output is correct
42 Correct 1 ms 8540 KB Output is correct
43 Correct 1 ms 8540 KB Output is correct
44 Correct 1 ms 8540 KB Output is correct
45 Correct 1 ms 8540 KB Output is correct
46 Correct 1 ms 8540 KB Output is correct
47 Correct 1 ms 8540 KB Output is correct
48 Correct 1 ms 8540 KB Output is correct
49 Correct 1 ms 2472 KB Output is correct
50 Correct 1 ms 8536 KB Output is correct
51 Correct 1 ms 8540 KB Output is correct
52 Correct 1 ms 8672 KB Output is correct
53 Correct 1 ms 8540 KB Output is correct
54 Correct 2 ms 8540 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 44012 KB Output is correct
2 Correct 32 ms 44084 KB Output is correct
3 Correct 31 ms 44012 KB Output is correct
4 Correct 32 ms 44020 KB Output is correct
5 Correct 32 ms 44020 KB Output is correct
6 Correct 5 ms 6396 KB Output is correct
7 Correct 40 ms 44020 KB Output is correct
8 Correct 24 ms 40436 KB Output is correct
9 Correct 28 ms 42992 KB Output is correct
10 Correct 27 ms 43060 KB Output is correct
11 Correct 27 ms 37992 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 9048 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 1 ms 8540 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 2 ms 8540 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 1 ms 8540 KB Output is correct
31 Correct 1 ms 8540 KB Output is correct
32 Correct 1 ms 8536 KB Output is correct
33 Correct 1 ms 8540 KB Output is correct
34 Correct 1 ms 8656 KB Output is correct
35 Correct 0 ms 2392 KB Output is correct
36 Correct 0 ms 2508 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 8540 KB Output is correct
39 Correct 1 ms 8540 KB Output is correct
40 Correct 1 ms 8536 KB Output is correct
41 Correct 1 ms 8540 KB Output is correct
42 Correct 1 ms 8540 KB Output is correct
43 Correct 1 ms 8540 KB Output is correct
44 Correct 1 ms 8540 KB Output is correct
45 Correct 1 ms 8656 KB Output is correct
46 Correct 1 ms 8540 KB Output is correct
47 Correct 1 ms 8540 KB Output is correct
48 Correct 1 ms 8540 KB Output is correct
49 Correct 1 ms 8540 KB Output is correct
50 Correct 1 ms 8540 KB Output is correct
51 Correct 1 ms 8540 KB Output is correct
52 Correct 1 ms 8656 KB Output is correct
53 Correct 1 ms 8540 KB Output is correct
54 Correct 1 ms 8540 KB Output is correct