Submission #891655

#	Time	Username	Problem	Language	Result	Execution time	Memory
891655		vjudge1	Mechanical Doll (IOI18_doll)	C++17	84 / 100	89 ms	11316 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

vi X, Y;

vector<pair<int, int> > VP;

int gen(int niv, int nr) {
    int id = X.size();
    X.push_back(0);
    Y.push_back(0);
    //cout << niv << " " << nr << "\n";
    if(niv == 1 && nr == 2) {
        return -id - 1; 
    } else if(niv == 1 && nr == 1) {
        X[id] = -1;
        return -id - 1;
    }
    
    if(nr <= (1 << (niv - 1))) {
        int S = gen(niv - 1, nr);
        Y[id] = S;
        X[id] = -1;
        return -id - 1;
    } else {
        Y[id] = gen(niv - 1, (1 << (niv - 1)));
        X[id] = gen(niv - 1, nr - (1 << (niv - 1)));
        return -id - 1;
    }
    return -id - 1;

}

void create_circuit(int M, vi A) {
    A.push_back(0);
    int niv = 1;
    while((1 << niv) <= A.size()) ++niv;
    gen(niv, A.size());
    vi C(M + 1, -1);

    vi Stare(X.size(), 0);

    int u = -1, p = 0;
    ////cout << "ASSIGN\n";
    do {
        if(u > 0) {
            u = -1;
        }
        int id = -u - 1;
        if(!Stare[id]) {
            Stare[id] ^= 1;
            if(X[id]) u = X[id];
            else {
                u = X[id] = A[p++];
            }
        } else {
            Stare[id] ^= 1;
            if(Y[id]) u = Y[id];
            else {
                u = Y[id] = A[p++];
            }
        }
    } while(u != 0);

    int nr0 = 0;
    for(auto &it : X) nr0 += !it;
    for(auto &it : Y) nr0 += !it;

    //cout << "In total " << nr0 << "\n";


    //for(auto it : Stare)
        //cout << it << " ";
    //cout << "\n";

    //cout << "C: ";
    //for(auto it : C) 
        //cout << it << " ";
    //cout << "\n";
    //cout << "X: ";
    //for(auto it : X) 
        //cout << it << " ";
    //cout << "\n";
    //cout << "Y: ";
    //for(auto it : Y) 
        //cout << it << " ";
    //cout << "\n";
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while((1 << niv) <= A.size()) ++niv;
      |           ~~~~~~~~~~~^~~~~~~~~~~

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