oj.uz

Submission #75463

# Submission time Handle Problem Language Result Execution time Memory
75463 2018-09-09T20:49:16 Z dimatc Mechanical Doll (IOI18_doll) C++14
0 / 100
 8 ms 9932 KB 
#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(600005), Y(600005);
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++) {
    cout<<X[i]<<" "<<Y[i]<<'\n';
  }*/

  answer(C, X, Y);
}

Compilation message

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
      |          ~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 9932 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4940 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4940 KB state 'Y'
2 Halted 0 ms 0 KB -