oj.uz

Submission #613847

# Submission time Handle Problem Language Result Execution time Memory
613847 2022-07-30T12:03:51 Z fvogel499 Mechanical Doll (IOI18_doll) C++17
37 / 100
 124 ms 11480 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define vi vector<int>

void create_circuit(int nbT, std::vector<int> b) {
    vi tOut(nbT+1, -1);
    int p2 = 1;
    while (p2*2 <= sz(b)) p2 *= 2;
    vi xSw(2*p2-1);
    vi ySw(2*p2-1);
    for (int i = 0; i < p2-1; i++) {
        assert(0 <= i && i < 2*p2-1);
        xSw[i] = -2*(i+1);
        ySw[i] = -2*(i+1)-1;
    }
    for (int i = p2-1; i < 2*p2-1; i++) {
        assert(0 <= i && i < 2*p2-1);
        xSw[i] = ySw[i] = -1;
    }
    ySw[2*p2-2] = 0;
    vi ptr(2*p2-1);
    for (int i = 0; i < p2/2; i++) ptr[i] = 0;
    vector<pair<int, int>> to;
    assert(sz(b) <= p2*2-1);
    for (int i = 0; i < p2*2-1; i++) {
        int x = 0;
        while (x < p2-1) {
            assert(0 <= i && i < 2*p2-1);
            ptr[x] ^= 1;
            if (ptr[x] == 1) {
                x = -xSw[x]-1;
            }
            else {
                x = -ySw[x]-1;
            }
        }
        assert(0 <= x && x < 2*p2-1);
        to.pb({x, ptr[x]});
        ptr[x] ^= 1;
    }
    int lenSeg = (sz(b)+1/2);
    int startPos = p2-1;
    int endPos = startPos+lenSeg-1;
    int curToIdx = 0;
    for (int i : b) {
        while (curToIdx < sz(to) && !(startPos <= to[curToIdx].first && to[curToIdx].first <= endPos)) {
            curToIdx++;
        }
        assert(curToIdx < sz(to));
        if (to[curToIdx].second == 0) {
            xSw[to[curToIdx].first] = i;
        }
        else {
            ySw[to[curToIdx].first] = i;
        }
        curToIdx++;
    }
    answer(tOut, xSw, ySw);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 109 ms 10560 KB Output is partially correct
3 Partially correct 121 ms 10496 KB Output is partially correct
4 Partially correct 110 ms 10996 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 109 ms 10560 KB Output is partially correct
3 Partially correct 121 ms 10496 KB Output is partially correct
4 Partially correct 110 ms 10996 KB Output is partially correct
5 Partially correct 121 ms 11480 KB Output is partially correct
6 Partially correct 124 ms 11280 KB Output is partially correct
7 Partially correct 117 ms 11376 KB Output is partially correct
8 Partially correct 112 ms 11164 KB Output is partially correct
9 Partially correct 106 ms 10552 KB Output is partially correct
10 Partially correct 112 ms 11216 KB Output is partially correct
11 Partially correct 113 ms 11056 KB Output is partially correct
12 Partially correct 103 ms 10572 KB Output is partially correct
13 Partially correct 110 ms 10684 KB Output is partially correct
14 Partially correct 109 ms 10740 KB Output is partially correct
15 Partially correct 111 ms 10864 KB Output is partially correct
16 Partially correct 3 ms 596 KB Output is partially correct
17 Correct 56 ms 5900 KB Output is correct
18 Partially correct 109 ms 10532 KB Output is partially correct
19 Partially correct 108 ms 10536 KB Output is partially correct
20 Partially correct 115 ms 11264 KB Output is partially correct
21 Partially correct 115 ms 11052 KB Output is partially correct
22 Partially correct 109 ms 11116 KB Output is partially correct