Submission #75978

#	Time	Username	Problem	Language	Result	Execution time	Memory
75978		dimatc	Mechanical Doll (IOI18_doll)	C++14	37 / 100	108 ms	10364 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;

int sw, k, H, leaves;
vector<int> X(400615), Y(400615);

void add(vector<int> &V2, vector<int> &V1, vector<int> &A) {
    for (auto x : V1) {
        if (k == H) {
            if (leaves > A.size() - 1) X[x-1] = -1, leaves++;
            else X[x-1] = A[leaves++];
        } else {
            ++sw;
            X[x-1] = -sw;
            V2.push_back(sw);
        }
    }
    for (auto x: V1) {
        if (k == H) {
            if (leaves > A.size() - 1) Y[x-1] = -1, leaves++;
            else Y[x-1] = A[leaves++];
        } else {
            ++sw;
            Y[x-1] = -sw;
            V2.push_back(sw);
        }
    }
    V1.clear();
}

void create_circuit(int M, std::vector<int> A) {
    vector<int> C(M + 1), V1, V2;

    int N = A.size()+1;
    for (H=0; (1<<H) < N; H++);

    k = 1; sw=1;
    V1.push_back(sw);
    while (k <= H) {
        if (!V1.size()) add(V1, V2, A);
        else add(V2, V1, A);
        ++k;
    }
    Y[sw-1]=0;
    for (int i=0; i<M+1; i++) C[i]=-1;

    X.resize(leaves-1);
    Y.resize(leaves-1);
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void add(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
doll.cpp:11:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |             if (leaves > A.size() - 1) X[x-1] = -1, leaves++;
      |                 ~~~~~~~^~~~~~~~~~~~~~
doll.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             if (leaves > A.size() - 1) Y[x-1] = -1, leaves++;
      |                 ~~~~~~~^~~~~~~~~~~~~~

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