oj.uz

Submission #75123

# Submission time Handle Problem Language Result Execution time Memory
75123 2018-09-08T12:29:36 Z imeimi2000 Mechanical Doll (IOI18_doll) C++17
100 / 100
 114 ms 10460 KB 
#include "doll.h"

using namespace std;

int n;
int seg[1 << 19];

int bitRev(int x, int n) {
    int r = 0;
    while (n >>= 1) {
        r <<= 1;
        r ^= (x & 1);
        x >>= 1;
    }
    return r;
}

const int inf = 1e9;
void create_circuit(int m, vector<int> A) {
    int sz = 1;
    A.push_back(0);
    n = A.size();
    while (sz < n) sz <<= 1;
    for (int i = 0; i < sz; ++i) seg[i + sz] = inf;
    for (int i = 0, j = 0; i < sz; ++i) {
        int k = bitRev(i, sz);
        if (k < sz - n) continue;
        seg[k + sz] = A[j++];
    }
    int SN = 0;
    vector<int> X, Y;
    for (int i = sz; --i; ) {
        if (seg[i << 1] == seg[i << 1 | 1]) {
            seg[i] = seg[i << 1];
            continue;
        }
        int S = SN++;
        seg[i] = -(S + 1);
        X.push_back(seg[i << 1]);
        Y.push_back(seg[i << 1 | 1]);
    }
    for (int i = 0; i < SN; ++i) {
        if (X[i] == inf) X[i] = seg[1];
        if (Y[i] == inf) Y[i] = seg[1];
    }
    answer(vector<int>(m + 1, seg[1]), X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 4940 KB Output is correct
3 Correct 44 ms 4884 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1044 KB Output is correct
6 Correct 72 ms 6584 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 4940 KB Output is correct
3 Correct 44 ms 4884 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1044 KB Output is correct
6 Correct 72 ms 6584 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 70 ms 7528 KB Output is correct
9 Correct 85 ms 8120 KB Output is correct
10 Correct 95 ms 10460 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 4940 KB Output is correct
3 Correct 44 ms 4884 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1044 KB Output is correct
6 Correct 72 ms 6584 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 70 ms 7528 KB Output is correct
9 Correct 85 ms 8120 KB Output is correct
10 Correct 95 ms 10460 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 96 ms 9856 KB Output is correct
15 Correct 56 ms 7092 KB Output is correct
16 Correct 96 ms 9564 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 110 ms 10068 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 24 ms 3236 KB Output is correct
3 Correct 37 ms 3308 KB Output is correct
4 Correct 49 ms 3880 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 24 ms 3236 KB Output is correct
3 Correct 37 ms 3308 KB Output is correct
4 Correct 49 ms 3880 KB Output is correct
5 Correct 89 ms 9476 KB Output is correct
6 Correct 92 ms 9120 KB Output is correct
7 Correct 79 ms 9260 KB Output is correct
8 Correct 96 ms 8904 KB Output is correct
9 Correct 49 ms 6324 KB Output is correct
10 Correct 105 ms 8152 KB Output is correct
11 Correct 114 ms 8492 KB Output is correct
12 Correct 67 ms 7640 KB Output is correct
13 Correct 70 ms 6736 KB Output is correct
14 Correct 64 ms 6744 KB Output is correct
15 Correct 60 ms 6964 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 62 ms 6680 KB Output is correct
18 Correct 66 ms 7572 KB Output is correct
19 Correct 63 ms 7608 KB Output is correct
20 Correct 84 ms 8720 KB Output is correct
21 Correct 87 ms 8612 KB Output is correct
22 Correct 91 ms 8480 KB Output is correct