Submission #587458

#	Time	Username	Problem	Language	Result	Execution time	Memory
587458		definitelynotmee	Mechanical Doll (IOI18_doll)	C++17	100 / 100	67 ms	10136 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    if(N == 1){
        vector<int> C(M+1), X, Y;
        C[0] = A[0];
        C[A[0]] = 0;
        answer(C,X,Y);
        return;
    }

    std::vector<int> C(M + 1);
    C[0] = A[0];
    for (int i = 1; i <= M; ++i) {
        C[i] = -1;
    }
    A.erase(A.begin());
    N--;

    array<vector<int>,2> to;
    auto create =[&](){
        int ret = to[0].size();
        for(int i = 0; i < 2; i++)
            to[i].push_back(-1);
        return ret; 
    };
    auto parse =[&](int id){
        return id*-1-1;
    };

    auto gen =[&](int id, int level, vector<int>& v, auto gen)->int{        
        if(id+(1<<level) >= v.size())
            return -1;
        
        int arrid = create();
        array<int,2> ret = {gen(id,level+1,v,gen),gen(id+(1<<level),level+1,v,gen)};
        for(int i = 0; i < 2; i++){
            if(ret[i] >= 0){
                to[i][arrid] = parse(ret[i]);
            } else {
                to[i][arrid] = v[id+(1<<level)*i];
            }
        }
        return arrid;
    };
    
    int logg = log2(N)+1;
    //cout << "logg = " << logg << '\n';
    matrix<int> task(logg);

    for(int i = 0; i < logg-1; i++){
        create();
        if((1<<(logg-i-1))&N)
            to[0][i] = 0;
        else to[0][i] = -1;
        to[1][i] = parse(i+1);
    }
    create();
    if(1&N)
        to[0][logg-1] = 0;
    else to[0][logg-1] = -1;
    to[1][logg-1] = 0;

    int id = 0, ptr = 0;
    vector<int> state(logg);

    while(id!=logg){
        state[id]^=1;

        if(!state[id]){
            id = id + 1;
        } else {
            if(to[0][id] == 0){
                task[id].push_back(A[ptr]);
                ptr++;
            }
            id = 0;
        }
    }
    // for(int i = 0; i < logg; i++){
    //     cout << "task[" << i << "] = ";
    //     for(int j : task[i])
    //         cout << j << ' ';
    //     cout << '\n';
    // }
    for(int i = 0; i < logg-1; i++){
        if(to[0][i] == 0){
            to[0][i] = parse(gen(0,0,task[i],gen));
        }
    }
    if(to[0][logg-1] == 0){
        to[0][logg-1] = task[logg-1].back();
    }

    answer(C, to[0], to[1]);
}

Compilation message (stderr)

doll.cpp: In instantiation of 'create_circuit(int, std::vector<int>)::<lambda(int, int, std::vector<int>&, auto:23)> [with auto:23 = create_circuit(int, std::vector<int>)::<lambda(int, int, std::vector<int>&, auto:23)>]':
doll.cpp:99:49:   required from here
doll.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if(id+(1<<level) >= v.size())
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~

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