oj.uz

Submission #75239

# Submission time Handle Problem Language Result Execution time Memory
75239 2018-09-08T18:44:23 Z mammamia Mechanical Doll (IOI18_doll) C++14
100 / 100
 160 ms 11612 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

int tokill, swcnt;
bool state[400555];
vector<int> X(400555), Y(400555);

void build(int root, int height, bool orientation){

    //cout<<root<<" "<<orientation<<" "<<(1<<height)<<" \n";
    if((1<<height) <= tokill){
        tokill-= (1<<height);
        X[root-1] = -1;
        return;
    }

    if(height == 0) {
        return;
    }

    swcnt++;
    if (!orientation) {
        X[root - 1] = -swcnt;
    } else {
        Y[root - 1] = -swcnt;
    }
    int aux = swcnt;
    build(aux, height - 1, 0);
    build(aux, height - 1, 1);

}

int nextElement;

void dfs(int root){
    if(!state[(-root)-1]){
        // X
        state[-root-1] = !state[-root-1];
        if(X[-root-1] >= 0){
            X[-root-1] = nextElement;
        } else {
            dfs(X[-root-1]);
        }
    }else{
        state[-root-1] = !state[-root-1];
        if(Y[-root-1] >= 0){
            Y[-root-1] = nextElement;
        } else {
            dfs(Y[-root-1]);
        }
    }
}

void create_circuit(int M, vector<int> A) {

    int N = A.size();
    A.push_back(0);


    int height = 0;
    int aux = N+1;
    while((1<<(height)) < aux){
        height++;
    }

    //cout<<height<<"\n";
    // exits to kill
    tokill = (1<<height) - (N+1);
    //cout<<"tokill "<<tokill<<"\n";
    swcnt = 1;

    build(1, height-1, 0);
    build(1, height-1, 1);
    vector<int> C (M+1);

    for(int i=0; i<=M; ++i){
        C[i] = -1;
    }

    for(int i=0; i<N+1; ++i){
        nextElement = A[i];
        dfs(-1);
    }

    X.resize(swcnt);
    Y.resize(swcnt);

    /*
    for(auto el: C){
        cout<<el<<" ";
    }
    cout<<"\n";
    for(auto el: X){
        cout<<el<<" ";
    }
    cout<<"\n";
    for(auto el: Y){
        cout<<el<<" ";
    }
    cout<<"\n";
     */
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 57 ms 6220 KB Output is correct
3 Correct 45 ms 6532 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 13 ms 4556 KB Output is correct
6 Correct 71 ms 8192 KB Output is correct
7 Correct 3 ms 3404 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 57 ms 6220 KB Output is correct
3 Correct 45 ms 6532 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 13 ms 4556 KB Output is correct
6 Correct 71 ms 8192 KB Output is correct
7 Correct 3 ms 3404 KB Output is correct
8 Correct 84 ms 8680 KB Output is correct
9 Correct 90 ms 9272 KB Output is correct
10 Correct 131 ms 11612 KB Output is correct
11 Correct 2 ms 3404 KB Output is correct
12 Correct 3 ms 3404 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 57 ms 6220 KB Output is correct
3 Correct 45 ms 6532 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 13 ms 4556 KB Output is correct
6 Correct 71 ms 8192 KB Output is correct
7 Correct 3 ms 3404 KB Output is correct
8 Correct 84 ms 8680 KB Output is correct
9 Correct 90 ms 9272 KB Output is correct
10 Correct 131 ms 11612 KB Output is correct
11 Correct 2 ms 3404 KB Output is correct
12 Correct 3 ms 3404 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct
14 Correct 125 ms 11104 KB Output is correct
15 Correct 83 ms 8224 KB Output is correct
16 Correct 129 ms 10840 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 2 ms 3404 KB Output is correct
19 Correct 3 ms 3404 KB Output is correct
20 Correct 129 ms 11344 KB Output is correct
21 Correct 2 ms 3404 KB Output is correct
22 Correct 3 ms 3404 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 95 ms 7276 KB Output is correct
3 Correct 76 ms 7276 KB Output is correct
4 Correct 160 ms 9404 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 95 ms 7276 KB Output is correct
3 Correct 76 ms 7276 KB Output is correct
4 Correct 160 ms 9404 KB Output is correct
5 Correct 126 ms 10728 KB Output is correct
6 Correct 119 ms 10436 KB Output is correct
7 Correct 126 ms 10544 KB Output is correct
8 Correct 122 ms 10180 KB Output is correct
9 Correct 78 ms 7280 KB Output is correct
10 Correct 117 ms 10016 KB Output is correct
11 Correct 159 ms 9696 KB Output is correct
12 Correct 100 ms 7496 KB Output is correct
13 Correct 81 ms 7856 KB Output is correct
14 Correct 84 ms 7996 KB Output is correct
15 Correct 79 ms 8160 KB Output is correct
16 Correct 8 ms 3532 KB Output is correct
17 Correct 73 ms 7536 KB Output is correct
18 Correct 80 ms 7540 KB Output is correct
19 Correct 76 ms 7540 KB Output is correct
20 Correct 128 ms 9912 KB Output is correct
21 Correct 119 ms 9760 KB Output is correct
22 Correct 125 ms 9824 KB Output is correct