oj.uz

Submission #612008

# Submission time Handle Problem Language Result Execution time Memory
612008 2022-07-29T09:58:44 Z M_W Mechanical Doll (IOI18_doll) C++17
26 / 100
 96 ms 22448 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int N, cnter = 0;
vector<int> adj[100001];
vector<int> X(400002), Y(400002);
vector<int> C(200002);
vector<int> ord;
bitset<400002> mark;

void chk(int a, int vv, int val, int bit){
  if((1 << (bit + 1)) > adj[a].size() - 1){
      ord.push_back(val); ord.push_back(val | (1 << bit));
      return;
    }

    chk(a, vv * 2, val, bit + 1);
    chk(a, vv * 2 + 1, val | (1 << bit), bit + 1);
}

void rechk(int a, int vv, int val, int bit){
  if((1 << (bit + 1)) > adj[a].size() - 1){
      if(adj[a][val] == -1) mark[vv * 2] = 1; else mark[vv * 2] = 0;

      if(adj[a][val | (1 << bit)] == -1) mark[vv * 2 + 1] = 1; else mark[vv * 2 + 1] = 0;

      mark[vv] = mark[vv * 2] & mark[vv * 2 + 1];
      return;
    }

    rechk(a, vv * 2, val, bit + 1);
    rechk(a, vv * 2 + 1, val | (1 << bit), bit + 1);
    mark[vv] = mark[vv * 2] & mark[vv * 2 + 1];
}

void build(int a, int vv, int cur, int pa, int val, int bit){
    if((1 << (bit + 1)) > adj[a].size() - 1){
      X[abs(cur)] = adj[a][val] == -1 ? pa : adj[a][val];
      Y[abs(cur)] = adj[a][val | (1 << bit)] == -1 ? pa : adj[a][val | (1 << bit)];
      return;
    }

    if(mark[vv * 2]){
      X[abs(cur)] = pa;
      Y[abs(cur)] = --cnter;
      build(a, vv * 2 + 1, cnter, pa, val | (1 << bit), bit + 1);
    }
    else if(mark[vv * 2 + 1]){
      X[abs(cur)] = pa;
      Y[abs(cur)] = --cnter;
      build(a, vv * 2, cnter, pa, val, bit + 1);
    }
    else{
      X[abs(cur)] = --cnter;
      build(a, vv * 2, cnter, pa, val, bit + 1);
      Y[abs(cur)] = --cnter;
      build(a, vv * 2 + 1, cnter, pa, val | (1 << bit), bit + 1);
    }
}

void create_circuit(int M, vector<int> A) {
    N = A.size();
    for(int i = 0; i < N - 1; i++) adj[A[i]].push_back(A[i + 1]);
    adj[A[N - 1]].push_back(0);

    C[0] = A[0];
    for(int i = 1; i <= M; i++){
        if(adj[i].size() == 0) continue;
        if(adj[i].size() == 1) C[i] = adj[i][0];
        else{
            C[i] = --cnter;
            int j = 0;
            for(; j <= 20; j++){
              if((1 << j) >= adj[i].size()) break;
            }
            vector<int> tmp((1 << j), 0);
            chk(i, 1, 0, 0);

            for(int k = 0; k < (1 << j) - adj[i].size(); k++) tmp[ord[k]] = -1;
            int idx = 0;
            for(auto x : adj[i]){
              while(tmp[idx] == -1) idx++;
              tmp[idx] = x;
              idx++;
            }

            adj[i] = tmp; rechk(i, 1, 0, 0);
            build(i, 1, cnter, cnter, 0, 0);
            ord.clear();
        }
    }
    vector<int> CA, XA, YA;
    for(int i = 1; i <= abs(cnter); i++){
      XA.push_back(X[i]); YA.push_back(Y[i]);
    }
    for(int i = 0; i <= M; i++) CA.push_back(C[i]);
    answer(CA, XA, YA);
}

Compilation message

doll.cpp: In function 'void chk(int, int, int, int)':
doll.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   if((1 << (bit + 1)) > adj[a].size() - 1){
      |      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void rechk(int, int, int, int)':
doll.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if((1 << (bit + 1)) > adj[a].size() - 1){
      |      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void build(int, int, int, int, int, int)':
doll.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if((1 << (bit + 1)) > adj[a].size() - 1){
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |               if((1 << j) >= adj[i].size()) break;
      |                  ~~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:79:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int k = 0; k < (1 << j) - adj[i].size(); k++) tmp[ord[k]] = -1;
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 31 ms 10820 KB Output is correct
3 Correct 21 ms 10236 KB Output is correct
4 Correct 4 ms 6588 KB Output is correct
5 Correct 12 ms 7856 KB Output is correct
6 Correct 31 ms 12360 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 31 ms 10820 KB Output is correct
3 Correct 21 ms 10236 KB Output is correct
4 Correct 4 ms 6588 KB Output is correct
5 Correct 12 ms 7856 KB Output is correct
6 Correct 31 ms 12360 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 47 ms 12612 KB Output is correct
9 Correct 47 ms 13120 KB Output is correct
10 Correct 73 ms 16064 KB Output is correct
11 Correct 3 ms 6588 KB Output is correct
12 Correct 3 ms 6484 KB Output is correct
13 Correct 4 ms 6484 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 31 ms 10820 KB Output is correct
3 Correct 21 ms 10236 KB Output is correct
4 Correct 4 ms 6588 KB Output is correct
5 Correct 12 ms 7856 KB Output is correct
6 Correct 31 ms 12360 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 47 ms 12612 KB Output is correct
9 Correct 47 ms 13120 KB Output is correct
10 Correct 73 ms 16064 KB Output is correct
11 Correct 3 ms 6588 KB Output is correct
12 Correct 3 ms 6484 KB Output is correct
13 Correct 4 ms 6484 KB Output is correct
14 Correct 86 ms 17080 KB Output is correct
15 Correct 48 ms 12096 KB Output is correct
16 Correct 77 ms 14928 KB Output is correct
17 Correct 3 ms 6484 KB Output is correct
18 Correct 3 ms 6484 KB Output is correct
19 Correct 3 ms 6588 KB Output is correct
20 Correct 96 ms 16424 KB Output is correct
21 Correct 3 ms 6584 KB Output is correct
22 Correct 3 ms 6484 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 43 ms 13432 KB Output is correct
3 Runtime error 41 ms 22448 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 43 ms 13432 KB Output is correct
3 Runtime error 41 ms 22448 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -