oj.uz

Submission #587582

# Submission time Handle Problem Language Result Execution time Memory
587582 2022-07-02T06:09:07 Z alireza_kaviani Mechanical Doll (IOI18_doll) C++17
100 / 100
 122 ms 15332 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define SZ(x)   int((x).size())
#define X       first
#define Y       second
#define sep     ' '

const int MAXN = 5e5 + 10;

int curInd = 1 , rev[MAXN];
vector<pii> res;

int solve(vector<int> vec , int n){
    int flag = 1;
    for(int i = 0 ; i < SZ(vec) ; i++){
        if(vec[i] != vec[0]){
            flag = 0;
        }
    }
    if(flag){
        return vec[0];
    }
    int root = curInd++ , ptr = 0 , ind = SZ(res);
    res.push_back({-1 , -1});
    vector<int> left , right;
    for(int i = 0 ; i < n / 2 ; i++){
        left.push_back(vec[ptr++]);
        right.push_back(vec[ptr++]);
    }
    int lc = solve(left , n / 2);
    int rc = solve(right , n / 2);
    res[ind] = {lc , rc};
    return -root;
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    int n = 1 , k = 0;
    while(n < SZ(A)){
        n *= 2;
        k++;
    }
    for(int i = 0 ; i < n ; i++){
        rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (k - 1)));
    }
    vector<int> B(n , 0);
    for(int i = 0 ; i < n - SZ(A) ; i++){
        B[rev[i]] = -1;
    }
    int ptr = 0;
    for(int i = 0 ; i < n ; i++){
        if(B[i] == 0){
            B[i] = A[ptr++];
        }
    }
    int root = solve(B , n);
    vector<int> C , x , y;
    for(int i = 0 ; i <= M ; i++){
        C.push_back(-1);
        //cout << i << sep << -1 << endl;
    }
    for(int i = 0 ; i < SZ(res) ; i++){
        x.push_back(res[i].X);
        y.push_back(res[i].Y);
        //cout << -(i + 1) << sep << res[i].X << sep << res[i].Y << endl;
    }
    answer(C , x , y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:60:9: warning: unused variable 'root' [-Wunused-variable]
   60 |     int root = solve(B , n);
      |         ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 41 ms 6688 KB Output is correct
3 Correct 41 ms 5868 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1612 KB Output is correct
6 Correct 59 ms 8936 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 0 ms 212 KB Output is correct
2 Correct 41 ms 6688 KB Output is correct
3 Correct 41 ms 5868 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1612 KB Output is correct
6 Correct 59 ms 8936 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 75 ms 10992 KB Output is correct
9 Correct 83 ms 11300 KB Output is correct
10 Correct 113 ms 15332 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 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 41 ms 6688 KB Output is correct
3 Correct 41 ms 5868 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1612 KB Output is correct
6 Correct 59 ms 8936 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 75 ms 10992 KB Output is correct
9 Correct 83 ms 11300 KB Output is correct
10 Correct 113 ms 15332 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 108 ms 15176 KB Output is correct
15 Correct 88 ms 10588 KB Output is correct
16 Correct 106 ms 14372 KB Output is correct
17 Correct 0 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 122 ms 15248 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 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 256 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 22 ms 7408 KB Output is correct
3 Correct 24 ms 7476 KB Output is correct
4 Correct 25 ms 7992 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 22 ms 7408 KB Output is correct
3 Correct 24 ms 7476 KB Output is correct
4 Correct 25 ms 7992 KB Output is correct
5 Correct 102 ms 12828 KB Output is correct
6 Correct 119 ms 13824 KB Output is correct
7 Correct 104 ms 13868 KB Output is correct
8 Correct 109 ms 12992 KB Output is correct
9 Correct 56 ms 9400 KB Output is correct
10 Correct 93 ms 11416 KB Output is correct
11 Correct 98 ms 13348 KB Output is correct
12 Correct 91 ms 9768 KB Output is correct
13 Correct 83 ms 9944 KB Output is correct
14 Correct 70 ms 9940 KB Output is correct
15 Correct 75 ms 9932 KB Output is correct
16 Correct 3 ms 576 KB Output is correct
17 Correct 63 ms 8080 KB Output is correct
18 Correct 68 ms 9800 KB Output is correct
19 Correct 76 ms 9696 KB Output is correct
20 Correct 109 ms 13572 KB Output is correct
21 Correct 97 ms 13356 KB Output is correct
22 Correct 109 ms 13400 KB Output is correct