oj.uz

Submission #218186

# Submission time Handle Problem Language Result Execution time Memory
218186 2020-04-01T11:48:28 Z anonymous Mechanical Doll (IOI18_doll) C++14
12 / 100
 100 ms 11296 KB 
#include "doll.h"
#include<vector>
#include<iostream>
#include<cassert>
#define MAXN 200005
using namespace std;
int N, L, V=-1, id;
bool state[MAXN];
vector<int> X, Y, C, Seq;

int build(int x, int d) {
    if (x == 1 && d == 0) {
        return(69);
    } else if (x == 0) {return(-1);}
    assert(d > 0);
    int cur = V;
    V--;
    X[-cur-1] = build(x-min(x,(1<<(d-1))), d-1);
    Y[-cur-1] = build(min(x,(1<<(d-1))), d-1);
    return(cur);
}

int log(int x) {
    return(x <= 1 ? 0 : log(x/2) + 1);
}

void simulate(int u) {
    if (id == N+1) {return;}
    if (state[-u] == 0) {
        state[-u] = 1;
        if (X[-u-1] == 69) {
            X[-u-1] = Seq[id];
            id++;
            simulate(-1);
        } else {
            simulate(X[-u-1]);
        }
    } else {
        state[-u] = 0;
        if (Y[-u-1] == 69) {
            Y[-u-1] = Seq[id];
            id++;
            simulate(-1);
        } else {
            simulate(Y[-u-1]);
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
  N = A.size(), L = log(N+1);
  if ((1<<L) < N+1) {L++;}
  for (int i=0; i<=M; i++) {
    C.push_back(-1);
  }
  for (int i=0; i<N+L; i++) {
    X.push_back(0);
    Y.push_back(0);
  }
  Seq = A;
  Seq.push_back(0);
  build(N+1, L);
  while (X.back() == 0 && Y.back() == 0) {
    X.pop_back();
    Y.pop_back();
  }
  simulate(-1);
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 4564 KB Output is correct
3 Correct 54 ms 4436 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 78 ms 5544 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 4564 KB Output is correct
3 Correct 54 ms 4436 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 78 ms 5544 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 100 ms 7200 KB Output is correct
9 Correct 97 ms 7616 KB Output is correct
10 Runtime error 54 ms 11296 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 4564 KB Output is correct
3 Correct 54 ms 4436 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 78 ms 5544 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 100 ms 7200 KB Output is correct
9 Correct 97 ms 7616 KB Output is correct
10 Runtime error 54 ms 11296 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 76 ms 5704 KB Output is correct
3 Correct 78 ms 5692 KB Output is correct
4 Runtime error 54 ms 9104 KB Execution killed with signal 11

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 76 ms 5704 KB Output is correct
3 Correct 78 ms 5692 KB Output is correct
4 Runtime error 54 ms 9104 KB Execution killed with signal 11