Submission #75470

#	Time	Username	Problem	Language	Result	Execution time	Memory
75470		dimatc	Mechanical Doll (IOI18_doll)	C++14	37 / 100	259 ms	24592 KiB

doll

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

int height;

struct node {
    int nr;
    bool u;
    node *x;
    node *y;
};
node *H;

std::vector<int> X(400005), Y(400005);
void build(int nr, int h, node* p) {
    //cout<<"!"<<p->nr<<'\n';

    if (h == height) {
        p->x = p->y = H;
            //cout<<"!"<<p->nr<<"\n";
        return;
    }
    X[p->nr -1] = -2*nr;
    Y[p->nr -1] = -(2*nr+1);
    p->x = new node({2*nr, 0, 0, 0});
    build(2*nr, h+1, p->x);
    p->y = new node({2*nr + 1, 0, 0, 0});
    build(2*nr + 1, h+1, p->y);
}

void create_circuit(int M, std::vector<int> A) {
  A.push_back(0);

  std::vector<int> C(M + 1);

  height = ceil(log2(A.size()));
  //cout<<height<<'\n';
  int leaves = (1<< (int)(ceil(log2(A.size())))) - 1;
  //cout<<"Leaves = "<<leaves<<'\n';

  H = new node({1,0,0,0});
  build(1, 1, H);
  int k=0; //insert 0 in a
  while (k<A.size()) { //check
     //   cout<<"k="<<k<<'\n';
    node* p=H;
    while (p->y != H) { //switch u before if
        p->u = !(p->u);
        if ((p->u)) {
            p=p->x;
        } else {
            p=p->y;
        }
       // cout<<p->nr<<'.';
    }
    if (!(p->u)) {
        p->x = new node({A[k], 0,0,0});
        X[p->nr -1]=A[k];
        ++k;
    } else {
        p->y = new node({A[k],0,0,0});
        Y[p->nr -1]=A[k];
        ++k;
    }
    p->u = !(p->u);
  }
  //cout<<"!!!!!!K"<<k<<'\n';
  for (int i=0; i<M+1; i++) C[i]=-1;
  X.resize(leaves); // x-1
  Y.resize(leaves);

  for (int i=0; i<X.size(); i++) {
    if (X[i]==0) X[i]=-1;
    if (Y[i]==0 && i!=X.size()-1) Y[i]=-1;
    //cout<<X[i]<<" "<<Y[i]<<'\n';
  }

  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:45:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   while (k<A.size()) { //check
      |          ~^~~~~~~~~
doll.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i=0; i<X.size(); i++) {
      |                 ~^~~~~~~~~
doll.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     if (Y[i]==0 && i!=X.size()-1) Y[i]=-1;
      |                    ~^~~~~~~~~~~~

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