oj.uz

Submission #767148

# Submission time Handle Problem Language Result Execution time Memory
767148 2023-06-26T12:41:41 Z oyber Mechanical Doll (IOI18_doll) C++14
100 / 100
 87 ms 12972 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, int remaining) {
    //printf("%d %d\n", num, remaining);
    //printf("s: %d\n", num);
    if (num <= 2) {
      x = 0;
      y = 0;
      ys.push_back(0);
      xs.push_back(0);
      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};
    y = add_switch(s1);
    ys.push_back(-y);
    int i = xs.size();
    xs.push_back(-1);
    //printf("t: %d %d\n", x, y);

    int a = min(num/2, remaining);
    switches[y].gen_childs(num/2, a);
    remaining -= a;

    if (remaining > 0) {
      Switch s2 = Switch{1, 1, 0};
      x = add_switch(s2);
      xs[i] = -x;
      switches[x].gen_childs(num/2, remaining);
    }
  }

  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 == 0) { 
    not_used--;
    if (not_used == 0) {
      ys[s-1] = 0;
      return;
    }
    next = -1;
    if (ai < n) {
      next = a[ai];
    }
    //printf("k: %d %d\n", next, not_used);
    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});
  int b = 1;
  while (b < n+1) {
    b *= 2;
  }
  switches[s].gen_childs(b, n+1);
  sim_switches(1);

  vector<int> C(M + 1);
  C[0] = -1;
  for (int i = 1; i <= M; ++i) {
    C[i] = -1;
  }
  //print_tree();
  //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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 32 ms 5068 KB Output is correct
3 Correct 28 ms 5364 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 44 ms 6984 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 32 ms 5068 KB Output is correct
3 Correct 28 ms 5364 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 44 ms 6984 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 55 ms 9528 KB Output is correct
9 Correct 58 ms 10008 KB Output is correct
10 Correct 87 ms 12972 KB Output is correct
11 Correct 0 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 32 ms 5068 KB Output is correct
3 Correct 28 ms 5364 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 44 ms 6984 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 55 ms 9528 KB Output is correct
9 Correct 58 ms 10008 KB Output is correct
10 Correct 87 ms 12972 KB Output is correct
11 Correct 0 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 85 ms 12420 KB Output is correct
15 Correct 61 ms 9028 KB Output is correct
16 Correct 79 ms 12192 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 296 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 83 ms 12676 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 304 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 49 ms 7080 KB Output is correct
3 Correct 57 ms 7092 KB Output is correct
4 Correct 74 ms 9856 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 49 ms 7080 KB Output is correct
3 Correct 57 ms 7092 KB Output is correct
4 Correct 74 ms 9856 KB Output is correct
5 Correct 81 ms 10524 KB Output is correct
6 Correct 78 ms 10228 KB Output is correct
7 Correct 81 ms 10376 KB Output is correct
8 Correct 77 ms 10032 KB Output is correct
9 Correct 47 ms 7076 KB Output is correct
10 Correct 76 ms 10056 KB Output is correct
11 Correct 79 ms 9912 KB Output is correct
12 Correct 50 ms 7348 KB Output is correct
13 Correct 53 ms 7700 KB Output is correct
14 Correct 51 ms 7828 KB Output is correct
15 Correct 51 ms 7916 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 47 ms 6692 KB Output is correct
18 Correct 61 ms 7332 KB Output is correct
19 Correct 49 ms 7316 KB Output is correct
20 Correct 76 ms 9928 KB Output is correct
21 Correct 76 ms 9852 KB Output is correct
22 Correct 75 ms 9912 KB Output is correct