oj.uz

Submission #1099859

# Submission time Handle Problem Language Result Execution time Memory
1099859 2024-10-12T05:38:23 Z model_code Hieroglyphs (IOI24_hieroglyphs) C++17
34 / 100
 104 ms 25472 KB 
// incorrect/felix-wa-jumps-2.cpp

#include<bits/stdc++.h>
#include "hieroglyphs.h"

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ii = pair<int, int>;

int ALPHABET_SIZE = 0;

bool is_subsequence(const vi& a, const vi& b) {
    int j = 0;
    for (int x : a) {
        if (j < (int)b.size() && b[j] == x) {
            j++;
        }
    }
    return j == (int)b.size();
}

vi get_candidate(const vi& a, const vi& b) {
    int n = a.size();
    int m = b.size();

    vi occ_a(ALPHABET_SIZE, 0);
    vi occ_b(ALPHABET_SIZE, 0);
    for (int i=0; i < n; ++i) {
        occ_a[a[i]]++;
    }
    for (int i=0; i < m; ++i) {
        occ_b[b[i]]++;
    }

    vi c;
    queue<int> qa;
    queue<int> qb;

    for (int i=0; i < n; ++i) {
        if (occ_a[a[i]] <= occ_b[a[i]]) {
            qa.push(i);
        }
    }
    for (int i=0; i < m; ++i) {
        if (occ_a[b[i]] > occ_b[b[i]]) {
            qb.push(i);
        }
    }

    int i_a_curr = 0;
    int i_b_curr = 0;
    int i_a_next = 0;
    int i_b_next = 0;
    vi occ_a_curr = vi(occ_a);
    vi occ_a_next = vi(occ_a);
    vi occ_b_curr = vi(occ_b);
    vi occ_b_next = vi(occ_b);

    while(!qa.empty() && !qb.empty()) {
        while(i_a_next < qa.front()) {
            occ_a_next[a[i_a_next]]--;
            i_a_next++;
        }
        while(i_b_next < qb.front()) {
            occ_b_next[b[i_b_next]]--;
            i_b_next++;
        }

        int x = a[i_a_next];
        int y = b[i_b_next];

        int occ_x = occ_a_next[x];
        int occ_y = occ_b_next[y];

        bool a_good = (occ_a_next[y] >= occ_y && occ_b_curr[x] > occ_b_next[x]);
        bool b_good = (occ_b_next[x] >= occ_x && occ_a_curr[y] > occ_a_next[y]);

        if (a_good && b_good) return {-1};
        if (!a_good && !b_good) return {-1};

        if(a_good) {
            c.push_back(x);
            qa.pop();
            while(i_a_curr <= i_a_next) {
                occ_a_curr[a[i_a_curr]]--;
                i_a_curr++;
            }
            while(b[i_b_curr] != x) {
                occ_b_curr[b[i_b_curr]]--;
                i_b_curr++;
            }
            occ_b_curr[b[i_b_curr]]--;
            i_b_curr++;
        }
        else {
            c.push_back(y);
            qb.pop();
            while(i_b_curr <= i_b_next) {
                occ_b_curr[b[i_b_curr]]--;
                i_b_curr++;
            }
            while(a[i_a_curr] != y) {
                occ_a_curr[a[i_a_curr]]--;
                i_a_curr++;
            }
            occ_a_curr[a[i_a_curr]]--;
            i_a_curr++;
        }
    }

    while(!qa.empty()) {
        c.push_back(a[qa.front()]);
        qa.pop();
    }
    while(!qb.empty()) {
        c.push_back(b[qb.front()]);
        qb.pop();
    }

    return ((is_subsequence(a, c) && is_subsequence(b, c)) ? c : vi({-1}));
}



bool verify_jump(const vi& a, const vi& b, const vi& c) {
    if (c == vi({-1})) return false;
    if (c == vi()) return true; 
    int n = a.size();
    int m = b.size();
    int l = c.size();

    vi occ_a(ALPHABET_SIZE, 0);
    vi occ_b(ALPHABET_SIZE, 0);
    vi occ_c(ALPHABET_SIZE, 0);
    vvi pos_a(ALPHABET_SIZE);
    vvi pos_b(ALPHABET_SIZE);
    vvi pos_c(ALPHABET_SIZE);
    for (int i=0; i < n; ++i) {
        occ_a[a[i]]++;
        pos_a[a[i]].push_back(i);
    }
    for (int i=0; i < m; ++i) {
        occ_b[b[i]]++;
        pos_b[b[i]].push_back(i);
    }
    for (int i=0; i < l; ++i) {
        occ_c[c[i]]++;
        pos_c[c[i]].push_back(i);
    }

    vi pos_c_idx(ALPHABET_SIZE);
    vi jump_left(l);
    for (int i=0; i < l; ++i) jump_left[i] = i;
    int c_idx = 0;

    for (int j=0; j < m; ++j) {
        
        if (b[j] == c[c_idx]) {
            pos_c_idx[b[j]]++;
            c_idx++;
            if (c_idx == l) break;
        }
        else {
            int idx = pos_c_idx[b[j]];
            if (idx < occ_c[b[j]]) {
                jump_left[pos_c[b[j]][idx]] = min(jump_left[pos_c[b[j]][idx]], c_idx);
                //pos_c_idx[b[j]]++;
            }
        }
        
    }

    vi jump_right(l);
    for (int i=0; i < l; ++i) jump_right[i] = i;
    c_idx--;
    
    for (int i=n-1; i > -1; --i) {
         
        if (a[i] == c[c_idx]) {
            pos_c_idx[a[i]]--;
            c_idx--;
            if (c_idx < 0) break;
        }
        else {
            int idx = pos_c_idx[a[i]]-1;
            if (idx > -1) {
                jump_right[pos_c[a[i]][idx]] = max(jump_right[pos_c[a[i]][idx]], c_idx);
                //pos_c_idx[a[i]]--;
            }
        }
        
    }

    vector<ii> stack_jump;


    for (int k=0; k < l; ++k) {
        while (!stack_jump.empty() && stack_jump.back().second < k) {
            stack_jump.pop_back();
        }
        if (!stack_jump.empty() && stack_jump.back().first >= jump_left[k]) {
            return false;
        }
        while (!stack_jump.empty() && stack_jump.back().second < jump_right[k]) {
            stack_jump.pop_back();
        }
        stack_jump.emplace_back(k, jump_right[k]);
        
    }

    
   

   
    return true;
}

bool verify(const vi& a, const vi& b, const vi& c) {
    return verify_jump(a, b, c) && verify_jump(b, a, c);
}

vector<int> ucs(vector<int> a, vector<int> b) {
    for (int x : a) ALPHABET_SIZE = max(ALPHABET_SIZE, x+1);
    for (int x : b) ALPHABET_SIZE = max(ALPHABET_SIZE, x+1);

    vi c = get_candidate(a, b);
    if (verify(a, b, c)) return c;
    return {-1};
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 83 ms 21128 KB Output is correct
6 Correct 18 ms 5332 KB Output is correct
7 Correct 15 ms 5336 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 83 ms 21128 KB Output is correct
6 Correct 18 ms 5332 KB Output is correct
7 Correct 15 ms 5336 KB Output is correct
8 Correct 68 ms 25228 KB Output is correct
9 Correct 70 ms 25400 KB Output is correct
10 Correct 76 ms 25224 KB Output is correct
11 Correct 70 ms 25232 KB Output is correct
12 Correct 68 ms 25236 KB Output is correct
13 Correct 73 ms 25200 KB Output is correct
14 Correct 82 ms 25232 KB Output is correct
15 Correct 68 ms 25228 KB Output is correct
16 Correct 73 ms 25228 KB Output is correct
17 Correct 70 ms 25272 KB Output is correct
18 Correct 9 ms 17504 KB Output is correct
19 Correct 9 ms 17220 KB Output is correct
20 Correct 9 ms 17636 KB Output is correct
21 Correct 11 ms 17676 KB Output is correct
22 Correct 41 ms 22324 KB Output is correct
23 Correct 67 ms 25304 KB Output is correct
24 Correct 70 ms 25296 KB Output is correct
25 Correct 68 ms 25424 KB Output is correct
26 Correct 49 ms 23020 KB Output is correct
27 Correct 74 ms 25324 KB Output is correct
28 Correct 74 ms 25272 KB Output is correct
29 Correct 45 ms 25224 KB Output is correct
30 Correct 43 ms 25220 KB Output is correct
31 Correct 68 ms 25232 KB Output is correct
32 Correct 67 ms 25232 KB Output is correct
33 Correct 81 ms 25472 KB Output is correct
34 Correct 39 ms 24592 KB Output is correct
35 Correct 71 ms 25232 KB Output is correct
36 Correct 72 ms 25232 KB Output is correct
37 Correct 55 ms 25264 KB Output is correct
38 Correct 75 ms 25256 KB Output is correct
39 Correct 67 ms 25392 KB Output is correct
40 Correct 45 ms 25220 KB Output is correct
41 Correct 71 ms 25192 KB Output is correct
42 Correct 49 ms 25224 KB Output is correct
43 Correct 47 ms 25224 KB Output is correct
44 Correct 51 ms 25224 KB Output is correct
45 Correct 44 ms 25228 KB Output is correct
46 Correct 49 ms 25280 KB Output is correct
47 Correct 42 ms 25224 KB Output is correct
48 Correct 43 ms 25224 KB Output is correct
49 Correct 47 ms 25220 KB Output is correct
50 Correct 76 ms 25232 KB Output is correct
51 Correct 80 ms 25224 KB Output is correct
52 Correct 43 ms 25224 KB Output is correct
53 Correct 41 ms 25256 KB Output is correct
54 Correct 45 ms 25220 KB Output is correct
55 Correct 51 ms 25220 KB Output is correct
56 Correct 82 ms 25376 KB Output is correct
57 Correct 71 ms 25252 KB Output is correct
58 Correct 69 ms 25396 KB Output is correct
59 Correct 68 ms 25228 KB Output is correct
60 Correct 48 ms 25224 KB Output is correct
61 Correct 78 ms 25220 KB Output is correct
62 Correct 47 ms 25220 KB Output is correct
63 Correct 67 ms 25372 KB Output is correct
64 Correct 76 ms 25220 KB Output is correct
65 Correct 46 ms 25224 KB Output is correct
66 Correct 74 ms 25240 KB Output is correct
67 Correct 72 ms 25232 KB Output is correct
68 Correct 46 ms 25232 KB Output is correct
69 Correct 1 ms 344 KB Output is correct
70 Correct 0 ms 348 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4840 KB Output is correct
2 Correct 31 ms 4916 KB Output is correct
3 Correct 25 ms 4028 KB Output is correct
4 Correct 24 ms 3832 KB Output is correct
5 Correct 28 ms 4468 KB Output is correct
6 Correct 13 ms 1948 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 28 ms 5196 KB Output is correct
17 Correct 15 ms 2396 KB Output is correct
18 Correct 18 ms 3136 KB Output is correct
19 Correct 11 ms 1796 KB Output is correct
20 Correct 27 ms 4016 KB Output is correct
21 Correct 12 ms 2136 KB Output is correct
22 Correct 12 ms 2396 KB Output is correct
23 Correct 16 ms 4800 KB Output is correct
24 Incorrect 28 ms 4772 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 25228 KB Output is correct
2 Correct 70 ms 25400 KB Output is correct
3 Correct 76 ms 25224 KB Output is correct
4 Correct 70 ms 25232 KB Output is correct
5 Correct 68 ms 25236 KB Output is correct
6 Correct 73 ms 25200 KB Output is correct
7 Correct 82 ms 25232 KB Output is correct
8 Correct 68 ms 25228 KB Output is correct
9 Correct 73 ms 25228 KB Output is correct
10 Correct 70 ms 25272 KB Output is correct
11 Correct 9 ms 17504 KB Output is correct
12 Correct 9 ms 17220 KB Output is correct
13 Correct 9 ms 17636 KB Output is correct
14 Correct 11 ms 17676 KB Output is correct
15 Correct 41 ms 22324 KB Output is correct
16 Correct 67 ms 25304 KB Output is correct
17 Correct 70 ms 25296 KB Output is correct
18 Correct 68 ms 25424 KB Output is correct
19 Correct 49 ms 23020 KB Output is correct
20 Correct 32 ms 4840 KB Output is correct
21 Correct 31 ms 4916 KB Output is correct
22 Correct 25 ms 4028 KB Output is correct
23 Correct 24 ms 3832 KB Output is correct
24 Correct 28 ms 4468 KB Output is correct
25 Correct 13 ms 1948 KB Output is correct
26 Correct 14 ms 17476 KB Output is correct
27 Correct 13 ms 17576 KB Output is correct
28 Correct 10 ms 15704 KB Output is correct
29 Correct 13 ms 16784 KB Output is correct
30 Correct 12 ms 17576 KB Output is correct
31 Correct 13 ms 17596 KB Output is correct
32 Correct 13 ms 17684 KB Output is correct
33 Correct 14 ms 17676 KB Output is correct
34 Correct 22 ms 17932 KB Output is correct
35 Correct 38 ms 21416 KB Output is correct
36 Correct 50 ms 22048 KB Output is correct
37 Correct 37 ms 22008 KB Output is correct
38 Correct 45 ms 21880 KB Output is correct
39 Correct 43 ms 21800 KB Output is correct
40 Correct 86 ms 24004 KB Output is correct
41 Correct 71 ms 22696 KB Output is correct
42 Correct 31 ms 15592 KB Output is correct
43 Correct 40 ms 17084 KB Output is correct
44 Correct 50 ms 16948 KB Output is correct
45 Correct 30 ms 15504 KB Output is correct
46 Correct 71 ms 23016 KB Output is correct
47 Correct 71 ms 23256 KB Output is correct
48 Correct 104 ms 22996 KB Output is correct
49 Correct 74 ms 22512 KB Output is correct
50 Correct 81 ms 22504 KB Output is correct
51 Correct 76 ms 22516 KB Output is correct
52 Correct 62 ms 22788 KB Output is correct
53 Correct 58 ms 22532 KB Output is correct
54 Correct 88 ms 22684 KB Output is correct
55 Correct 20 ms 18620 KB Output is correct
56 Correct 42 ms 21788 KB Output is correct
57 Correct 41 ms 21856 KB Output is correct
58 Correct 60 ms 22232 KB Output is correct
59 Correct 49 ms 22036 KB Output is correct
60 Correct 61 ms 22180 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 14 ms 17476 KB Output is correct
11 Correct 13 ms 17576 KB Output is correct
12 Correct 10 ms 15704 KB Output is correct
13 Correct 13 ms 16784 KB Output is correct
14 Correct 12 ms 17576 KB Output is correct
15 Correct 13 ms 17596 KB Output is correct
16 Correct 13 ms 17684 KB Output is correct
17 Correct 14 ms 17676 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 2 ms 816 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 11 ms 17684 KB Output is correct
28 Correct 11 ms 17676 KB Output is correct
29 Correct 12 ms 17720 KB Output is correct
30 Correct 18 ms 17624 KB Output is correct
31 Correct 16 ms 17212 KB Output is correct
32 Correct 11 ms 17152 KB Output is correct
33 Incorrect 1 ms 348 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6
0.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 21128 KB Output is correct
9 Correct 18 ms 5332 KB Output is correct
10 Correct 15 ms 5336 KB Output is correct
11 Correct 68 ms 25228 KB Output is correct
12 Correct 70 ms 25400 KB Output is correct
13 Correct 76 ms 25224 KB Output is correct
14 Correct 70 ms 25232 KB Output is correct
15 Correct 68 ms 25236 KB Output is correct
16 Correct 73 ms 25200 KB Output is correct
17 Correct 82 ms 25232 KB Output is correct
18 Correct 68 ms 25228 KB Output is correct
19 Correct 73 ms 25228 KB Output is correct
20 Correct 70 ms 25272 KB Output is correct
21 Correct 9 ms 17504 KB Output is correct
22 Correct 9 ms 17220 KB Output is correct
23 Correct 9 ms 17636 KB Output is correct
24 Correct 11 ms 17676 KB Output is correct
25 Correct 41 ms 22324 KB Output is correct
26 Correct 67 ms 25304 KB Output is correct
27 Correct 70 ms 25296 KB Output is correct
28 Correct 68 ms 25424 KB Output is correct
29 Correct 49 ms 23020 KB Output is correct
30 Correct 74 ms 25324 KB Output is correct
31 Correct 74 ms 25272 KB Output is correct
32 Correct 45 ms 25224 KB Output is correct
33 Correct 43 ms 25220 KB Output is correct
34 Correct 68 ms 25232 KB Output is correct
35 Correct 67 ms 25232 KB Output is correct
36 Correct 81 ms 25472 KB Output is correct
37 Correct 39 ms 24592 KB Output is correct
38 Correct 71 ms 25232 KB Output is correct
39 Correct 72 ms 25232 KB Output is correct
40 Correct 55 ms 25264 KB Output is correct
41 Correct 75 ms 25256 KB Output is correct
42 Correct 67 ms 25392 KB Output is correct
43 Correct 45 ms 25220 KB Output is correct
44 Correct 71 ms 25192 KB Output is correct
45 Correct 49 ms 25224 KB Output is correct
46 Correct 47 ms 25224 KB Output is correct
47 Correct 51 ms 25224 KB Output is correct
48 Correct 44 ms 25228 KB Output is correct
49 Correct 49 ms 25280 KB Output is correct
50 Correct 42 ms 25224 KB Output is correct
51 Correct 43 ms 25224 KB Output is correct
52 Correct 47 ms 25220 KB Output is correct
53 Correct 76 ms 25232 KB Output is correct
54 Correct 80 ms 25224 KB Output is correct
55 Correct 43 ms 25224 KB Output is correct
56 Correct 41 ms 25256 KB Output is correct
57 Correct 45 ms 25220 KB Output is correct
58 Correct 51 ms 25220 KB Output is correct
59 Correct 82 ms 25376 KB Output is correct
60 Correct 71 ms 25252 KB Output is correct
61 Correct 69 ms 25396 KB Output is correct
62 Correct 68 ms 25228 KB Output is correct
63 Correct 48 ms 25224 KB Output is correct
64 Correct 78 ms 25220 KB Output is correct
65 Correct 47 ms 25220 KB Output is correct
66 Correct 67 ms 25372 KB Output is correct
67 Correct 76 ms 25220 KB Output is correct
68 Correct 46 ms 25224 KB Output is correct
69 Correct 74 ms 25240 KB Output is correct
70 Correct 72 ms 25232 KB Output is correct
71 Correct 46 ms 25232 KB Output is correct
72 Correct 1 ms 344 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 32 ms 4840 KB Output is correct
75 Correct 31 ms 4916 KB Output is correct
76 Correct 25 ms 4028 KB Output is correct
77 Correct 24 ms 3832 KB Output is correct
78 Correct 28 ms 4468 KB Output is correct
79 Correct 13 ms 1948 KB Output is correct
80 Correct 0 ms 348 KB Output is correct
81 Correct 0 ms 348 KB Output is correct
82 Correct 0 ms 348 KB Output is correct
83 Correct 0 ms 348 KB Output is correct
84 Correct 0 ms 348 KB Output is correct
85 Correct 0 ms 348 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 1 ms 348 KB Output is correct
88 Correct 0 ms 348 KB Output is correct
89 Correct 28 ms 5196 KB Output is correct
90 Correct 15 ms 2396 KB Output is correct
91 Correct 18 ms 3136 KB Output is correct
92 Correct 11 ms 1796 KB Output is correct
93 Correct 27 ms 4016 KB Output is correct
94 Correct 12 ms 2136 KB Output is correct
95 Correct 12 ms 2396 KB Output is correct
96 Correct 16 ms 4800 KB Output is correct
97 Incorrect 28 ms 4772 KB Output isn't correct
98 Halted 0 ms 0 KB -