oj.uz

Submission #75469

# Submission time Handle Problem Language Result Execution time Memory
75469 2018-09-09T21:06:37 Z dimatc Mechanical Doll (IOI18_doll) C++14
9 / 100
 328 ms 38008 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 6732 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 6732 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 6732 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 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 4 ms 3404 KB Output is partially correct
2 Partially correct 178 ms 20848 KB Output is partially correct
3 Partially correct 179 ms 20920 KB Output is partially correct
4 Partially correct 237 ms 23500 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 3404 KB Output is partially correct
2 Partially correct 178 ms 20848 KB Output is partially correct
3 Partially correct 179 ms 20920 KB Output is partially correct
4 Partially correct 237 ms 23500 KB Output is partially correct
5 Partially correct 259 ms 24616 KB Output is partially correct
6 Partially correct 237 ms 24248 KB Output is partially correct
7 Partially correct 225 ms 24456 KB Output is partially correct
8 Partially correct 233 ms 24012 KB Output is partially correct
9 Partially correct 156 ms 20948 KB Output is partially correct
10 Partially correct 328 ms 23932 KB Output is partially correct
11 Partially correct 232 ms 23652 KB Output is partially correct
12 Runtime error 159 ms 38008 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -