oj.uz

Submission #636766

# Submission time Handle Problem Language Result Execution time Memory
636766 2022-08-30T05:48:28 Z tabr Mechanical Doll (IOI18_doll) C++17
100 / 100
 127 ms 11720 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#ifdef tabr
void answer(vector<int> c, vector<int> x, vector<int> y) {
    debug(c);
    debug(x);
    debug(y);
}
#else
#include "doll.h"
#endif

void create_circuit(int m, vector<int> a) {
    a.emplace_back(0);
    int n = (int) a.size() - 1;
    int l = 31 - __builtin_clz(n);
    vector<int> x(l + 1), y(l + 1);
    for (int i = l; i >= 0; i--) {
        int v = l - i;
        if (i == 0) {
            x[v] = 0;
        } else {
            x[v] = v + 1;
        }
        y[v] = 0;
        if (n & (1 << i)) {
            if (i == 0) {
                y[v] = -1;
            } else {
                int z = (int) x.size();
                y[v] = z;
                for (int j = 0; j < (1 << i) - 1; j++) {
                    if (2 * j + 2 < (1 << i)) {
                        x.emplace_back(z + 2 * j + 1);
                        y.emplace_back(z + 2 * j + 2);
                    } else {
                        x.emplace_back(-1);
                        y.emplace_back(-1);
                    }
                }
            }
        }
    }
    debug(x);
    debug(y);
    for (int i = 0; i < (int) x.size(); i++) {
        x[i] = -1 - x[i];
        y[i] = -1 - y[i];
    }
    vector<int> c(m + 1, -1);
    c[0] = a[0];
    int v = 0;
    int cnt = 1;
    vector<int> sw(x.size());
    do {
        if (v >= 0) {
            debug(v);
            v = c[v];
        } else {
            if (!sw[~v]) {
                if (x[~v] == 0) {
                    x[~v] = a[cnt];
                    cnt++;
                }
                sw[~v] ^= 1;
                v = x[~v];
            } else {
                if (y[~v] == 0) {
                    y[~v] = a[cnt];
                    cnt++;
                }
                sw[~v] ^= 1;
                v = y[~v];
            }
        }
    } while (v != 0);
    answer(c, x, y);
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    create_circuit(4, {1, 2, 1, 3});
    return 0;
}
#endif

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 41 ms 4212 KB Output is correct
3 Correct 39 ms 4352 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 54 ms 6800 KB Output is correct
7 Correct 0 ms 224 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 41 ms 4212 KB Output is correct
3 Correct 39 ms 4352 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 54 ms 6800 KB Output is correct
7 Correct 0 ms 224 KB Output is correct
8 Correct 70 ms 7424 KB Output is correct
9 Correct 81 ms 8192 KB Output is correct
10 Correct 117 ms 11720 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 296 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 41 ms 4212 KB Output is correct
3 Correct 39 ms 4352 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 54 ms 6800 KB Output is correct
7 Correct 0 ms 224 KB Output is correct
8 Correct 70 ms 7424 KB Output is correct
9 Correct 81 ms 8192 KB Output is correct
10 Correct 117 ms 11720 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 103 ms 11232 KB Output is correct
15 Correct 68 ms 6988 KB Output is correct
16 Correct 105 ms 10932 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 105 ms 11380 KB Output is correct
21 Correct 1 ms 224 KB Output is correct
22 Correct 0 ms 224 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 62 ms 6240 KB Output is correct
3 Correct 59 ms 6260 KB Output is correct
4 Correct 106 ms 9468 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 62 ms 6240 KB Output is correct
3 Correct 59 ms 6260 KB Output is correct
4 Correct 106 ms 9468 KB Output is correct
5 Correct 127 ms 10748 KB Output is correct
6 Correct 98 ms 10536 KB Output is correct
7 Correct 103 ms 10624 KB Output is correct
8 Correct 104 ms 10268 KB Output is correct
9 Correct 62 ms 6276 KB Output is correct
10 Correct 97 ms 10160 KB Output is correct
11 Correct 99 ms 9764 KB Output is correct
12 Correct 61 ms 6536 KB Output is correct
13 Correct 64 ms 6776 KB Output is correct
14 Correct 63 ms 6720 KB Output is correct
15 Correct 77 ms 6880 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 58 ms 6440 KB Output is correct
18 Correct 65 ms 6468 KB Output is correct
19 Correct 60 ms 6532 KB Output is correct
20 Correct 113 ms 10012 KB Output is correct
21 Correct 94 ms 9864 KB Output is correct
22 Correct 97 ms 9860 KB Output is correct