oj.uz

Submission #75470

# Submission time Handle Problem Language Result Execution time Memory
75470 2018-09-09T21:09:33 Z dimatc Mechanical Doll (IOI18_doll) C++14
37 / 100
 259 ms 24592 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(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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 3404 KB Output is partially correct
2 Partially correct 164 ms 20984 KB Output is partially correct
3 Partially correct 143 ms 20872 KB Output is partially correct
4 Partially correct 208 ms 23548 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 3404 KB Output is partially correct
2 Partially correct 164 ms 20984 KB Output is partially correct
3 Partially correct 143 ms 20872 KB Output is partially correct
4 Partially correct 208 ms 23548 KB Output is partially correct
5 Partially correct 223 ms 24592 KB Output is partially correct
6 Partially correct 236 ms 24264 KB Output is partially correct
7 Partially correct 196 ms 24344 KB Output is partially correct
8 Partially correct 223 ms 24096 KB Output is partially correct
9 Partially correct 159 ms 20948 KB Output is partially correct
10 Partially correct 206 ms 23980 KB Output is partially correct
11 Partially correct 259 ms 23668 KB Output is partially correct
12 Partially correct 178 ms 21148 KB Output is partially correct
13 Partially correct 172 ms 21592 KB Output is partially correct
14 Partially correct 185 ms 21668 KB Output is partially correct
15 Partially correct 200 ms 21920 KB Output is partially correct
16 Partially correct 6 ms 4044 KB Output is partially correct
17 Correct 81 ms 15584 KB Output is correct
18 Partially correct 144 ms 21056 KB Output is partially correct
19 Partially correct 147 ms 21112 KB Output is partially correct
20 Partially correct 227 ms 23832 KB Output is partially correct
21 Partially correct 246 ms 23600 KB Output is partially correct
22 Partially correct 226 ms 23620 KB Output is partially correct