Submission #587569

#	Time	Username	Problem	Language	Result	Execution time	Memory
587569		alireza_kaviani	Mechanical Doll (IOI18_doll)	C++17	66.61 / 100	151 ms	16780 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     ' '

int curInd = 1;
vector<pii> res;

int solve(vector<int> vec){
    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++ , n = 1 , ptr = 0 , ind = SZ(res);
    res.push_back({-1 , -1});
    while(n < SZ(vec))  n *= 2;
    vector<int> left , right;
    for(int i = 0 ; i < SZ(vec) - n / 2 ; i++){
        left.push_back(vec[ptr++]);
        right.push_back(vec[ptr++]);
    }
    while(ptr < SZ(vec)){
        right.push_back(vec[ptr++]);
    }
    while(SZ(left) < SZ(right)){
        left.push_back(-1);
    }
    int lc = solve(left);
    int rc = solve(right);
    res[ind] = {lc , rc};
    return -root;
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    int root = solve(A);
    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:47:9: warning: unused variable 'root' [-Wunused-variable]
   47 |     int root = solve(A);
      |         ^~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 38.6089077416 / 56