Submission #587582

#	Time	Username	Problem	Language	Result	Execution time	Memory
587582		alireza_kaviani	Mechanical Doll (IOI18_doll)	C++17	100 / 100	122 ms	15332 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56