Submission #75469

#	Time	Username	Problem	Language	Result	Execution time	Memory
75469		dimatc	Mechanical Doll (IOI18_doll)	C++14	9 / 100	328 ms	38008 KiB

doll

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

/*struct nod {
    int nr;
    int x, y;
    bool u;
};

nod h[600010];
node *H;

void build(int n, vector<int> A) {
    A.push_back(0);//!!!
    int k=0, leaves = (1<<(ceil(log2(n))))-1;
    while (k<=leaves) {
        if (k > leaves/2) {
            h[++k] = {k, 1, 1, false};
        } else {
            h[++k]={k, 2*k, 2*k+1, false}
        }
    }

    k=0;
    while (k<=n) {
        int p=1

        if (!h[p].u) {
            p=2*n;
            if (p>leaves) {
                h[p/2].x = A[k];
            }
        } else {
            p=2*n+1;
            if (p>leaves) {
                h[p/2].y = A[k];
            }
        }
    }

    int k = 1, leaves = (1<<(ceil(log2(n)))-1);
    H = new node(k, 0, 0);
    node p = H;
    while (k <= leaves) {
        if (k >= leaves/2) {
            p.x = p.y = H;
        } else {
            p.x = new no
        }
    }
}

void build(int nr, int h, node *p) {
    if (h== htree) {
        p.x = p.y = H;
        return;
    }
    p.x = new node(nr*2, 0,0,0,0);
    build(2*nr, h+1, p.x);
    p.y = new node(nr*2+1, 0,0,0,0);
    build(2*nr+1, h+1, p.x);
}*/

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:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   while (k<A.size()) { //check
      |          ~^~~~~~~~~
doll.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int i=0; i<X.size(); i++) {
      |                 ~^~~~~~~~~
doll.cpp:135:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     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: 0 / 56