Submission #278762

#	Time	Username	Problem	Language	Result	Execution time	Memory
278762		doowey	Mechanical Doll (IOI18_doll)	C++14	37 / 100	183 ms	12904 KiB

doll

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair

int id = -1;

vector<int> X,Y;

int build(vector<int> T){
    int cur = id;
    id -- ;
    if(T.size() == 2){
        X.push_back(T[0]);
        Y.push_back(T[1]);
        return cur;
    }
    bool eq = true;
    for(int i = 0 ; i < T.size(); i ++ )
        if(T[i] != T[0]) eq = false;
    if(eq){
        X.push_back(T[0]);
        Y.push_back(T[0]);
        return cur;
    }
    vector<int> s1, s2;
    for(int i = 0 ; i < T.size(); i ++ ){
        if(i % 2 == 0) s1.push_back(T[i]);
        else s2.push_back(T[i]);
    }
    int sz = X.size();
    X.push_back(0);
    Y.push_back(0);
    int lef = build(s1);
    int rig = build(s2);
    X[sz] = lef;
    Y[sz] = rig;
    return cur;
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    int lg = 1;
    while(lg < A.size())
        lg *= 2;
    vector<int> comp;
    while(comp.size() + A.size() < lg)
        comp.push_back(-1);
    for(auto x : A)
        comp.push_back(x);
    vector<int> C(M+1);
    for(int i = 0 ; i <= M ; i ++ )
        C[i] = -1;
    build(comp);
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'int build(std::vector<int>)':
doll.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0 ; i < T.size(); i ++ )
      |                     ~~^~~~~~~~~~
doll.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0 ; i < T.size(); i ++ ){
      |                     ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while(lg < A.size())
      |           ~~~^~~~~~~~~~
doll.cpp:54:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     while(comp.size() + A.size() < lg)
      |           ~~~~~~~~~~~~~~~~~~~~~~~^~~~

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