oj.uz

Submission #620501

# Submission time Handle Problem Language Result Execution time Memory
620501 2022-08-03T06:35:15 Z snasibov05 Mechanical Doll (IOI18_doll) C++14
81.1563 / 100
 177 ms 14732 KB 
#include "doll.h"
#include <queue>

using namespace std;

void create_circuit(int m, vector<int> a) {

    int n = a.size();
    vector<vector<int>> to(m+1);
    to[0].push_back(a[0]);
    for (int i = 0; i < n-1; ++i){
        to[a[i]].push_back(a[i+1]);
    }
    to[a[n-1]].push_back(0);

    vector<int> x, y;
    vector<bool> state;
    int cur = -1;
    vector<int> c(m+1);

    for (int i = 0; i <= m; ++i){
        int k = 0, b = 1;
        while (to[i].size() > b) b *= 2, k++;

        if (k == 0){
            if (to[i].empty()) c[i] = 0;
            else c[i] = to[i][0];
            continue;
        }

        int src = cur;
        int mx = cur - b + 2;
        c[i] = cur--;

        queue<int> q;
        q.push(cur+1);
        while (!q.empty()){
            state.push_back(true);
            int p = q.front();
            q.pop();
            if (cur < mx) {
                x.push_back(0);
                y.push_back(0);
                continue;
            }
            x.push_back(cur--);
            y.push_back(cur--);
            q.push(x.back());
            q.push(y.back());
        }

        int rem = b - (int)to[i].size();
        for (int j = 0; j < to[i].size() - rem; ++j){
            int pos = src;
            for (int l = 0; l < k-1; ++l) {
                if (state[-pos-1]) {
                    state[-pos-1] = false;
                    pos = x[-pos-1];
                } else{
                    state[-pos-1] = true;
                    pos = y[-pos-1];
                }
            }
            if (state[-pos-1]) {
                state[-pos-1] = false;
                x[-pos-1] = to[i][j];
            } else{
                state[-pos-1] = true;
                y[-pos-1] = to[i][j];
            }
        }

        for (int j = (int)to[i].size() - rem; j < to[i].size(); ++j){
            int pos = src;
            for (int l = 0; l < k-1; ++l) {
                if (state[-pos-1]) {
                    state[-pos-1] = false;
                    pos = x[-pos-1];
                } else{
                    state[-pos-1] = true;
                    pos = y[-pos-1];
                }
            }
            if (state[-pos-1]) {
                state[-pos-1] = false;
                x[-pos-1] = src;
            } else{
                state[-pos-1] = true;
                y[-pos-1] = src;
            }

            pos = src;
            for (int l = 0; l < k-1; ++l) {
                if (state[-pos-1]) {
                    state[-pos-1] = false;
                    pos = x[-pos-1];
                } else{
                    state[-pos-1] = true;
                    pos = y[-pos-1];
                }
            }
            if (state[-pos-1]) {
                state[-pos-1] = false;
                x[-pos-1] = to[i][j];
            } else{
                state[-pos-1] = true;
                y[-pos-1] = to[i][j];
            }
        }
    }

    while (true){


        vector<int> pr(-cur), tp(-cur);
        for (int i = cur + 1; i <= m; ++i){
            if (i < 0) {
                if (x[-i-1] < 0) pr[-x[-i-1]-1] = i, tp[-x[-i-1]-1] = 1;
                if (y[-i-1] < 0) pr[-y[-i-1]-1] = i, tp[-y[-i-1]-1] = 2;
            } else{
                if (c[i] < 0) pr[-c[i]-1] = i, tp[-c[i]-1] = 3;
            }
        }

        vector<bool> del(-cur);
        bool flag = false;
        for (int i = -1; i > cur; --i){
            if (x[-i-1] != y[-i-1]) continue;

            if (tp[-i-1] == 1) x[-pr[-i-1]-1] = x[-i-1];
            else if (tp[-i-1] == 2) y[-pr[-i-1]-1] = y[-i-1];
            else c[pr[-i-1]] = x[-i-1];

            del[-i-1] = true;
            flag = true;
        }

        if (!flag) break;

        vector<int> nname(-cur);
        int ncur = -1;
        for (int i = -1; i > cur; --i){
            if (del[-i-1]) continue;
            nname[-i-1] = ncur--;
        }

        vector<int> xx(-ncur), yy(-ncur);
        for (int i = -1; i > cur; --i){
            if (del[-i-1]) continue;
            if (x[-i-1] > 0) xx[-nname[-i-1]-1] = x[-i-1];
            else xx[-nname[-i-1]-1] = nname[-x[-i-1]-1];
            if (y[-i-1] > 0) yy[-nname[-i-1]-1] = y[-i-1];
            else yy[-nname[-i-1]-1] = nname[-y[-i-1]-1];
        }
        for (int i = 0; i <= m; ++i){
            if (c[i] > 0) continue;
            c[i] = nname[-c[i]-1];
        }

        x = xx, y = yy;
        cur = ncur;

    }

    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:23:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |         while (to[i].size() > b) b *= 2, k++;
      |                ~~~~~~~~~~~~~^~~
doll.cpp:39:17: warning: unused variable 'p' [-Wunused-variable]
   39 |             int p = q.front();
      |                 ^
doll.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int j = 0; j < to[i].size() - rem; ++j){
      |                         ~~^~~~~~~~~~~~~~~~~~~~
doll.cpp:73:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int j = (int)to[i].size() - rem; j < to[i].size(); ++j){
      |                                               ~~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 27 ms 6732 KB Output is correct
3 Correct 19 ms 5540 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 3796 KB Output is correct
6 Correct 31 ms 8248 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 27 ms 6732 KB Output is correct
3 Correct 19 ms 5540 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 3796 KB Output is correct
6 Correct 31 ms 8248 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 49 ms 7884 KB Output is correct
9 Correct 53 ms 9340 KB Output is correct
10 Correct 79 ms 11436 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 292 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 27 ms 6732 KB Output is correct
3 Correct 19 ms 5540 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 3796 KB Output is correct
6 Correct 31 ms 8248 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 49 ms 7884 KB Output is correct
9 Correct 53 ms 9340 KB Output is correct
10 Correct 79 ms 11436 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 292 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 90 ms 11680 KB Output is correct
15 Correct 51 ms 6812 KB Output is correct
16 Correct 81 ms 9744 KB Output is correct
17 Correct 1 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 86 ms 11488 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 1 ms 284 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 40 ms 5852 KB Output is correct
3 Correct 77 ms 9232 KB Output is correct
4 Correct 151 ms 10648 KB Output is correct

Subtask #6
37.1562698192 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 40 ms 5852 KB Output is correct
3 Correct 77 ms 9232 KB Output is correct
4 Correct 151 ms 10648 KB Output is correct
5 Partially correct 101 ms 13276 KB Output is partially correct
6 Partially correct 121 ms 13880 KB Output is partially correct
7 Partially correct 105 ms 13656 KB Output is partially correct
8 Partially correct 111 ms 14272 KB Output is partially correct
9 Correct 115 ms 9316 KB Output is correct
10 Correct 177 ms 14268 KB Output is correct
11 Partially correct 137 ms 14732 KB Output is partially correct
12 Partially correct 83 ms 9932 KB Output is partially correct
13 Partially correct 82 ms 9512 KB Output is partially correct
14 Partially correct 68 ms 9348 KB Output is partially correct
15 Partially correct 71 ms 9132 KB Output is partially correct
16 Partially correct 2 ms 596 KB Output is partially correct
17 Partially correct 73 ms 8328 KB Output is partially correct
18 Partially correct 84 ms 8232 KB Output is partially correct
19 Partially correct 80 ms 8764 KB Output is partially correct
20 Partially correct 103 ms 11212 KB Output is partially correct
21 Partially correct 126 ms 13092 KB Output is partially correct
22 Partially correct 96 ms 10792 KB Output is partially correct