Submission #587578

#	Time	Username	Problem	Language	Result	Execution time	Memory
587578		alireza_kaviani	Mechanical Doll (IOI18_doll)	C++17	28 / 100	110 ms	12056 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 n){
    int flag = 1;
    for(int i = 0 ; i < SZ(vec) ; i++){
        if(vec[i] != vec[0]){
            flag = 0;
        }
    }
    if(flag && (SZ(vec) == n || SZ(vec) == 0)){
        return (SZ(vec) == 0 ? -1 : vec[0]);
    }
    int root = curInd++ , ptr = 0 , ind = SZ(res);
    res.push_back({-1 , -1});
    vector<int> left , right;
    int szleft = SZ(vec) - n / 2;
    for(int i = 0 ; i < min(SZ(vec) , n - SZ(vec)) ; i++){
        right.push_back(vec[ptr++]);
    }
    while(ptr < SZ(vec)){
        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;
    while(n < SZ(A))    n *= 2;
    int root = solve(A , 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 'int solve(std::vector<int>, int)':
doll.cpp:28:9: warning: unused variable 'szleft' [-Wunused-variable]
   28 |     int szleft = SZ(vec) - n / 2;
      |         ^~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:9: warning: unused variable 'root' [-Wunused-variable]
   46 |     int root = solve(A , n);
      |         ^~~~

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