oj.uz

Submission #767127

# Submission time Handle Problem Language Result Execution time Memory
767127 2023-06-26T12:05:01 Z oyber Mechanical Doll (IOI18_doll) C++14
37 / 100
 110 ms 14368 KB 
#include "doll.h"
#include <cstdio>
using namespace std;

vector<int> c;
vector<int> xs;
vector<int> ys;
vector<int> a;
int ai = 0;
int n = 0;

struct Switch;
extern Switch* switches;
int add_switch(Switch);

int not_used = 0;
struct Switch {
  int x;
  int y;
  int state;

  void gen_childs(int num) {
    //printf("s: %d\n", num);
    if (num <= 2) {
      xs.push_back(-1);
      ys.push_back(-1);
      not_used += 2;
      return;
    }
    /*if (num == 3) {
      Switch s = Switch{0, 0, 0};
      x = add_switch(s);
      xs.push_back(-x);
      ys.push_back(0);
      switches[x].gen_childs(2);
      return;
    }*/
    Switch s1 = Switch{-1, -1, 0};
    x = add_switch(s1);
    xs.push_back(-x);
    int i = ys.size();
    ys.push_back(0);
    //printf("t: %d %d\n", x, y);

    switches[x].gen_childs((num+1)/2);

    Switch s2 = Switch{-1, -1, 0};
    y = add_switch(s2);
    ys[i] = -y;

    switches[y].gen_childs((num+1)/2);
  }

  int get() {
    int next = x;
    if (state == 1) next = y;
    state = !state;
    return next;
  }
};

#define NUM_SWITCHES 1000000
Switch switches2[NUM_SWITCHES];
Switch* switches = switches2;
int index = 1;

int add_switch(Switch s) {
  switches[index] = s;
  index++;
  return index-1;
}

void print_tree() {
  printf("X: ");
  for (int i = 0; i < int(xs.size()); i++) {
    printf("%d, ", xs[i]);
  }
  printf("\n");

  printf("Y: ");
  for (int i = 0; i < int(ys.size()); i++) {
    printf("%d, ", ys[i]);
  }
  printf("\n");
}

void sim_switches(int s) {
  //print_tree();
  //printf("%d\n", s);
  int next = switches[s].get();
  if (next == -1) { 
    not_used--;
    if (not_used == 0) {
      ys[s-1] = 0;
      return;
    }
    if (ai < n) {
      next = a[ai];
      //printf("k: %d\n", next);
      if (switches[s].state == 1) {
        xs[s-1] = next;
        //printf("x: (%d %d)\n", s-1, next);
      } else {
        ys[s-1] = next;
        //printf("x: (%d %d)\n", s-1, next);
      }
      ai++;
    }
    sim_switches(1);
    return;
  }
  sim_switches(next);
}

void create_circuit(int M, std::vector<int> A) {
  a = A;
  int N = A.size();
  n = N;

  int s = add_switch(Switch{0,0,0});
  switches[s].gen_childs(N+1);
  sim_switches(1);

  vector<int> C(M + 1);
  C[0] = -1;
  for (int i = 1; i <= M; ++i) {
    C[i] = -1;
  }
  //C[A[N-1]] = 0;
  /*
  printf("C: ");
  for (int i = 0; i <= M; i++) {
    printf("%d, ", C[i]);
  }
  printf("\n");

  printf("X: ");
  for (int i = 0; i < int(xs.size()); i++) {
    printf("%d, ", xs[i]);
  }
  printf("\n");

  printf("Y: ");
  for (int i = 0; i < int(ys.size()); i++) {
    printf("%d, ", ys[i]);
  }
  printf("\n");
*/
  answer(C, xs, ys);
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 0 ms 212 KB Output is partially correct
2 Partially correct 91 ms 12204 KB Output is partially correct
3 Partially correct 91 ms 12220 KB Output is partially correct
4 Partially correct 97 ms 13556 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 91 ms 12204 KB Output is partially correct
3 Partially correct 91 ms 12220 KB Output is partially correct
4 Partially correct 97 ms 13556 KB Output is partially correct
5 Partially correct 110 ms 14368 KB Output is partially correct
6 Partially correct 100 ms 14036 KB Output is partially correct
7 Partially correct 104 ms 14112 KB Output is partially correct
8 Partially correct 100 ms 13820 KB Output is partially correct
9 Partially correct 89 ms 12284 KB Output is partially correct
10 Partially correct 97 ms 13776 KB Output is partially correct
11 Partially correct 98 ms 13596 KB Output is partially correct
12 Partially correct 91 ms 12460 KB Output is partially correct
13 Partially correct 94 ms 12716 KB Output is partially correct
14 Partially correct 93 ms 12724 KB Output is partially correct
15 Partially correct 92 ms 12848 KB Output is partially correct
16 Partially correct 3 ms 724 KB Output is partially correct
17 Correct 49 ms 7584 KB Output is correct
18 Partially correct 95 ms 12468 KB Output is partially correct
19 Partially correct 91 ms 12432 KB Output is partially correct
20 Partially correct 106 ms 13744 KB Output is partially correct
21 Partially correct 99 ms 13600 KB Output is partially correct
22 Partially correct 96 ms 13600 KB Output is partially correct