oj.uz

Submission #613930

# Submission time Handle Problem Language Result Execution time Memory
613930 2022-07-30T13:33:10 Z fvogel499 Mechanical Doll (IOI18_doll) C++17
37 / 100
 353 ms 39088 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)+1)/2;
    int startPos = p2-1;
    int endPos = startPos+lenSeg-1;
    int curToIdx = 0;
    bool used [2*p2-1];
    for (int i = 0; i < 2*p2-1; i++) {
        used[i] = true;
    }
    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
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 1 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 1 ms 212 KB Output is partially correct
2 Partially correct 345 ms 38080 KB Output is partially correct
3 Partially correct 327 ms 38076 KB Output is partially correct
4 Partially correct 319 ms 38580 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 345 ms 38080 KB Output is partially correct
3 Partially correct 327 ms 38076 KB Output is partially correct
4 Partially correct 319 ms 38580 KB Output is partially correct
5 Partially correct 346 ms 39088 KB Output is partially correct
6 Partially correct 340 ms 38868 KB Output is partially correct
7 Partially correct 336 ms 38916 KB Output is partially correct
8 Partially correct 333 ms 38788 KB Output is partially correct
9 Partially correct 324 ms 38068 KB Output is partially correct
10 Partially correct 334 ms 38660 KB Output is partially correct
11 Partially correct 337 ms 38640 KB Output is partially correct
12 Partially correct 320 ms 38144 KB Output is partially correct
13 Partially correct 337 ms 38236 KB Output is partially correct
14 Partially correct 336 ms 38296 KB Output is partially correct
15 Partially correct 319 ms 38328 KB Output is partially correct
16 Partially correct 7 ms 1492 KB Output is partially correct
17 Correct 161 ms 20012 KB Output is correct
18 Partially correct 314 ms 38228 KB Output is partially correct
19 Partially correct 322 ms 38312 KB Output is partially correct
20 Partially correct 343 ms 38684 KB Output is partially correct
21 Partially correct 321 ms 38684 KB Output is partially correct
22 Partially correct 353 ms 38620 KB Output is partially correct