oj.uz

Submission #587081

# Submission time Handle Problem Language Result Execution time Memory
587081 2022-07-01T09:41:13 Z Josia Mechanical Doll (IOI18_doll) C++14
100 / 100
 131 ms 15512 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;


vector<int> x;
vector<int> y;
void createTree (int v, int n, int next, int &count) {
    if (n > next/2) {
        if (next == 2) {
            x[v] = -2;
            y[v] = -2;
            return;
        }
        x[v] = count+1;
        y[v] = count+2;
        count += 2;

        createTree(x[v], next/2, next/2, count);
        createTree(y[v], n-(next/2), next/2, count);
    }
    else {
        if (next == 2) {
            x[v] = -2;
            y[v] = 0;
            return;
        }
        x[v] = count+1;
        y[v] = 0;
        count += 1;

        createTree(x[v], n, next/2, count);
    }
}





void create_circuit(int M, vector<int> A) {
    int N = A.size();



    if (N == 1) {
        vector<int> ans(M+1);
        ans[0] = A[0];
        answer(ans, {}, {});
        return;
    }


    x.assign(2*N, -1);
    y.assign(2*N, -1);
    // x.push_back(-1);
    // y.push_back(-1);


    int next = 1;
    while (next < N) {
        next *= 2;
    }

    // cerr << next << "\n";

    int count = 0;
    createTree(0, N, next, count);

    swap(x, y);

    // cerr << count << "\n";
    // for (int i = 0; i<N*2; i++) {
    //     cerr << x[i] << " " << y[i] << "\n";
    // }

    vector<int> c(M+1);

    c[0] = A[0];

    for (int i=1; i<=M; i++) c[i] = -1;


    vector<bool> swi(2*N, 0);

    A.push_back(0);

    vector<int> finalX, finalY;

    for (int i = 0; i<2*N; i++) {
        finalX.push_back(-(x[i]+1));
        finalY.push_back(-(y[i]+1));
    }


    // cerr << "\n";

    // for (int i=0; i<2*N; i++) {
    //     cerr << finalX[i] << " " << finalY[i] << "\n";
    // }

    for (int i=1; i<=N; i++) {
        int v = 0;
        while (true) {
            int now;
            if(swi[v]) now = y[v];
            else now = x[v];

            if (now == -2) {
                if(swi[v]) finalY[v] = A[i];
                else finalX[v] = A[i];
                swi[v] = !swi[v];
                break;
            }
            swi[v] = !swi[v];
            v = now;
        }
    }

    // cerr << "\n";

    // for (int i=0; i<2*N; i++) {
    //     cerr << finalX[i] << " " << finalY[i] << "\n";
    // }


    vector<int> resX(count+1);
    vector<int> resY(count+1);

    for (int i=0; i<=count; i++) {
        resX[i] = finalX[i];
        resY[i] = finalY[i];
    }

    answer(c, resX, resY);

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 45 ms 5560 KB Output is correct
3 Correct 34 ms 5196 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 61 ms 7716 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 45 ms 5560 KB Output is correct
3 Correct 34 ms 5196 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 61 ms 7716 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 76 ms 10228 KB Output is correct
9 Correct 77 ms 10540 KB Output is correct
10 Correct 117 ms 15512 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 45 ms 5560 KB Output is correct
3 Correct 34 ms 5196 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 61 ms 7716 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 76 ms 10228 KB Output is correct
9 Correct 77 ms 10540 KB Output is correct
10 Correct 117 ms 15512 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 109 ms 15124 KB Output is correct
15 Correct 75 ms 9836 KB Output is correct
16 Correct 106 ms 14928 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 114 ms 15176 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 300 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 1 ms 232 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 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 72 ms 8548 KB Output is correct
3 Correct 64 ms 8532 KB Output is correct
4 Correct 101 ms 12980 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 72 ms 8548 KB Output is correct
3 Correct 64 ms 8532 KB Output is correct
4 Correct 101 ms 12980 KB Output is correct
5 Correct 126 ms 13300 KB Output is correct
6 Correct 102 ms 13104 KB Output is correct
7 Correct 105 ms 13092 KB Output is correct
8 Correct 122 ms 12984 KB Output is correct
9 Correct 66 ms 8440 KB Output is correct
10 Correct 109 ms 12912 KB Output is correct
11 Correct 118 ms 12888 KB Output is correct
12 Correct 74 ms 8564 KB Output is correct
13 Correct 61 ms 8692 KB Output is correct
14 Correct 71 ms 8784 KB Output is correct
15 Correct 72 ms 8812 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 66 ms 8568 KB Output is correct
18 Correct 60 ms 8552 KB Output is correct
19 Correct 91 ms 8460 KB Output is correct
20 Correct 99 ms 12836 KB Output is correct
21 Correct 106 ms 12844 KB Output is correct
22 Correct 131 ms 12888 KB Output is correct