oj.uz

Submission #302708

# Submission time Handle Problem Language Result Execution time Memory
302708 2020-09-19T04:36:22 Z lohacho Mechanical Doll (IOI18_doll) C++14
100 / 100
 183 ms 10644 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int INF = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int lr[NS * 2];
vector<int> C;
vector<int> X, Y;

void make_tree(int num, int now, int to, int cnt){
    X.push_back(0), Y.push_back(0);
    if(now == to){
        if(cnt - (1 << (to - now)) >= 0){
            X[-num - 1] = -1;
        }
        return;
    }
    if(cnt - (1 << (to - now)) >= 0){
        X[-num - 1] = -1;
        Y[-num - 1] = -(int)Y.size() - 1;
        make_tree(-(int)Y.size() - 1, now + 1, to, cnt - (1 << (to - now)));
    }
    else{
        X[-num - 1] = -(int)X.size() - 1;
        make_tree(-(int)X.size() - 1, now + 1, to, cnt);
        Y[-num - 1] = -(int)Y.size() - 1;
        make_tree(-(int)Y.size() - 1, now + 1, to, cnt - (1 << (to - now)));
    }
}

pair < int, int > get(int num, int now, int to){
    if(!lr[-num-1]){
        lr[-num-1] = 1 - lr[-num-1];
        if(X[-num-1] == -1) return make_pair(0, 0);
        if(now == to) return make_pair(-num-1, 0);
        return get(X[-num-1], now + 1, to);
    }
    else{
        lr[-num-1] = 1 - lr[-num-1];
        if(now == to) return make_pair(-num-1, 1);
        return get(Y[-num-1], now + 1, to);
    }
}

void create_circuit(int M, std::vector<int> A) {
    A.push_back(0);
    C.resize(M + 1);
    int N = A.size();
    if(N == 2){
        C[0] = A[0], C[A[0]] = 0;
        answer(C, X, Y);
        return;
    }
    for(auto&i:C) i = -1;
    int dep = 1;
    while((1 << dep) < N){
        dep += 1;
    }
    make_tree(-1, 1, dep, (1 << dep) - N);
    int j = 0;
    for(int i = 0; i < (1 << dep); ++i){
        pair < int, int > val = get(-1, 1, dep);
        if(val.first){
            if(!val.second) X[val.first] = A[j++];
            else Y[val.first] = A[j++];
        }
    }
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 55 ms 4468 KB Output is correct
3 Correct 63 ms 4324 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 67 ms 6308 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 55 ms 4468 KB Output is correct
3 Correct 63 ms 4324 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 67 ms 6308 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 119 ms 6968 KB Output is correct
9 Correct 123 ms 7496 KB Output is correct
10 Correct 135 ms 10644 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 55 ms 4468 KB Output is correct
3 Correct 63 ms 4324 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 67 ms 6308 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 119 ms 6968 KB Output is correct
9 Correct 123 ms 7496 KB Output is correct
10 Correct 135 ms 10644 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 165 ms 10140 KB Output is correct
15 Correct 90 ms 6536 KB Output is correct
16 Correct 141 ms 9952 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 139 ms 10360 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 4 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 77 ms 5572 KB Output is correct
3 Correct 84 ms 5580 KB Output is correct
4 Correct 132 ms 8380 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 77 ms 5572 KB Output is correct
3 Correct 84 ms 5580 KB Output is correct
4 Correct 132 ms 8380 KB Output is correct
5 Correct 130 ms 9760 KB Output is correct
6 Correct 143 ms 9400 KB Output is correct
7 Correct 148 ms 9512 KB Output is correct
8 Correct 126 ms 9212 KB Output is correct
9 Correct 80 ms 5560 KB Output is correct
10 Correct 140 ms 9116 KB Output is correct
11 Correct 127 ms 8744 KB Output is correct
12 Correct 79 ms 5860 KB Output is correct
13 Correct 80 ms 6192 KB Output is correct
14 Correct 87 ms 6256 KB Output is correct
15 Correct 82 ms 6416 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 85 ms 6200 KB Output is correct
18 Correct 81 ms 5792 KB Output is correct
19 Correct 109 ms 5736 KB Output is correct
20 Correct 122 ms 8984 KB Output is correct
21 Correct 183 ms 8728 KB Output is correct
22 Correct 140 ms 8824 KB Output is correct