oj.uz

Submission #613933

# Submission time Handle Problem Language Result Execution time Memory
613933 2022-07-30T13:40:49 Z fvogel499 Mechanical Doll (IOI18_doll) C++17
100 / 100
 277 ms 33320 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+2;
    }
    for (int i = p2-1; i < 2*p2-1; i++) {
        assert(0 <= i && i < 2*p2-1);
        xSw[i] = ySw[i] = 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];
            }
            else {
                x = ySw[x];
            }
        }
        assert(0 <= x && x < 2*p2-1);
        to.pb({x, ptr[x]});
        ptr[x] ^= 1;
    }
    int lenSeg = (sz(b)+2)/2;
    int endPos = 2*p2-2;
    int startPos = endPos-lenSeg+1;
    int curToIdx = 0;
    bool used [2*p2-1];
    for (int i = 0; i < 2*p2-1; i++) {
        used[i] = false;
    }
    int otherPurposeX = 2*p2-2;
    while (otherPurposeX >= 0) {
        used[otherPurposeX] = true;
        if (otherPurposeX == 0) break;
        otherPurposeX = (otherPurposeX-1)/2;
    }
    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;
        }
        int x = to[curToIdx].first;
        while (x >= 0) {
            used[x] = true;
            if (x == 0) break;
            x = (x-1)/2;
        }
        curToIdx++;
    }
    set<int> usedSet;
    for (int i = 0; i < 2*p2-1; i++) if (used[i]) usedSet.insert(i);
    map<int, int> usedCompress;
    int kc2 = 0;
    for (int i : usedSet) {
        usedCompress[i] = kc2;
        kc2++;
    }
    vector<int> swCompX(sz(usedSet)), swCompY(sz(usedSet));
    for (int i = 0; i < 2*p2-1; i++) if (used[i]) {
        int iComp = usedCompress[i];
        int xVal = xSw[i];
        int yVal = ySw[i];
        if (usedSet.count(xVal)) {
            swCompX[iComp] = usedCompress[xVal];
        }
        else if (xVal < 0) {
            swCompX[iComp] = xVal;
        }
        else {
            swCompX[iComp] = 0;
        }
        if (usedSet.count(yVal)) {
            swCompY[iComp] = usedCompress[yVal];
        }
        else if (yVal < 0) {
            swCompY[iComp] = yVal;
        }
        else {
            swCompY[iComp] = 0;
        }
    }
    for (int i = 0; i < sz(swCompX); i++) {
        if (swCompX[i] < 0) {
            swCompX[i] *= -1;
        }
        else {
            swCompX[i] = -1-swCompX[i];
        }
        if (swCompY[i] < 0) {
            swCompY[i] *= -1;
        }
        else {
            swCompY[i] = -1-swCompY[i];
        }
    }
    swCompY[usedCompress[2*p2-2]] = 0;
    answer(tOut, swCompX, swCompY);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 91 ms 12288 KB Output is correct
3 Correct 87 ms 12424 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 1448 KB Output is correct
6 Correct 130 ms 17292 KB Output is correct
7 Correct 1 ms 296 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 91 ms 12288 KB Output is correct
3 Correct 87 ms 12424 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 1448 KB Output is correct
6 Correct 130 ms 17292 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 213 ms 23788 KB Output is correct
9 Correct 202 ms 24196 KB Output is correct
10 Correct 266 ms 33320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 0 ms 304 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 91 ms 12288 KB Output is correct
3 Correct 87 ms 12424 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 1448 KB Output is correct
6 Correct 130 ms 17292 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 213 ms 23788 KB Output is correct
9 Correct 202 ms 24196 KB Output is correct
10 Correct 266 ms 33320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 264 ms 32920 KB Output is correct
15 Correct 179 ms 23360 KB Output is correct
16 Correct 258 ms 32780 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 277 ms 33064 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
2 Correct 189 ms 22140 KB Output is correct
3 Correct 183 ms 22064 KB Output is correct
4 Correct 255 ms 30660 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 189 ms 22140 KB Output is correct
3 Correct 183 ms 22064 KB Output is correct
4 Correct 255 ms 30660 KB Output is correct
5 Correct 258 ms 31108 KB Output is correct
6 Correct 257 ms 30908 KB Output is correct
7 Correct 256 ms 30976 KB Output is correct
8 Correct 255 ms 30764 KB Output is correct
9 Correct 179 ms 22108 KB Output is correct
10 Correct 259 ms 30760 KB Output is correct
11 Correct 264 ms 30624 KB Output is correct
12 Correct 177 ms 22052 KB Output is correct
13 Correct 184 ms 22280 KB Output is correct
14 Correct 186 ms 22332 KB Output is correct
15 Correct 181 ms 22332 KB Output is correct
16 Correct 4 ms 980 KB Output is correct
17 Correct 147 ms 19340 KB Output is correct
18 Correct 185 ms 22100 KB Output is correct
19 Correct 182 ms 22116 KB Output is correct
20 Correct 259 ms 30812 KB Output is correct
21 Correct 255 ms 30740 KB Output is correct
22 Correct 259 ms 30752 KB Output is correct