Submission #611977

# Submission time Handle Problem Language Result Execution time Memory
611977 2022-07-29T09:21:24 Z M_W Mechanical Doll (IOI18_doll) C++17
53 / 100
123 ms 20832 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);

void build(int a, int cur, int pa, int val, int bit){
    if((1 << (bit + 1)) > adj[a].size() - 1){
      if(adj[a].size() - 1 >= (val | (1 << bit))){
        X[abs(cur)] = adj[a][val] == -1000000 ? pa : adj[a][val];
        Y[abs(cur)] = adj[a][val | (1 << bit)] == -1000000 ? pa : adj[a][val | (1 << bit)];
      }
      else{
        X[abs(cur)] = cur;
        Y[abs(cur)] = adj[a][val] == -1000000 ? pa : adj[a][val];
      }
      return;
    }
    
    if(adj[a].size() - 1 >= (val | (1 << bit))){
      X[abs(cur)] = --cnter;
      build(a, cnter, pa, val, bit + 1);
      Y[abs(cur)] = --cnter;
      build(a, cnter, pa, val | (1 << bit), bit + 1);
    }
    else{
      X[abs(cur)] = cur;
      Y[abs(cur)] = --cnter;
      build(a, cnter, pa, val, 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;
            for(int k = 0; k < (1 << j) - adj[i].size(); k++) tmp.push_back(-1000000);
            for(auto x : adj[i]) tmp.push_back(x);

            adj[i] = tmp;
            build(i, cnter, cnter, 0, 0);
        }
    }
    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 build(int, int, int, int, int)':
doll.cpp:10:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if((1 << (bit + 1)) > adj[a].size() - 1){
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp:11:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |       if(adj[a].size() - 1 >= (val | (1 << bit))){
      |          ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
doll.cpp:22:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |     if(adj[a].size() - 1 >= (val | (1 << bit))){
      |        ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |               if((1 << j) >= adj[i].size()) break;
      |                  ~~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:51:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for(int k = 0; k < (1 << j) - adj[i].size(); k++) tmp.push_back(-1000000);
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 29 ms 10884 KB Output is correct
3 Correct 23 ms 10452 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 18 ms 7852 KB Output is correct
6 Correct 35 ms 12372 KB Output is correct
7 Correct 5 ms 6484 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 29 ms 10884 KB Output is correct
3 Correct 23 ms 10452 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 18 ms 7852 KB Output is correct
6 Correct 35 ms 12372 KB Output is correct
7 Correct 5 ms 6484 KB Output is correct
8 Correct 55 ms 12876 KB Output is correct
9 Correct 47 ms 13372 KB Output is correct
10 Correct 70 ms 16320 KB Output is correct
11 Correct 4 ms 6484 KB Output is correct
12 Correct 4 ms 6612 KB Output is correct
13 Correct 5 ms 6584 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 29 ms 10884 KB Output is correct
3 Correct 23 ms 10452 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 18 ms 7852 KB Output is correct
6 Correct 35 ms 12372 KB Output is correct
7 Correct 5 ms 6484 KB Output is correct
8 Correct 55 ms 12876 KB Output is correct
9 Correct 47 ms 13372 KB Output is correct
10 Correct 70 ms 16320 KB Output is correct
11 Correct 4 ms 6484 KB Output is correct
12 Correct 4 ms 6612 KB Output is correct
13 Correct 5 ms 6584 KB Output is correct
14 Correct 84 ms 17364 KB Output is correct
15 Correct 47 ms 12304 KB Output is correct
16 Correct 94 ms 15196 KB Output is correct
17 Correct 4 ms 6580 KB Output is correct
18 Correct 4 ms 6576 KB Output is correct
19 Correct 4 ms 6584 KB Output is correct
20 Correct 83 ms 16684 KB Output is correct
21 Correct 3 ms 6484 KB Output is correct
22 Correct 3 ms 6580 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 6484 KB Output is partially correct
2 Correct 43 ms 13104 KB Output is correct
3 Partially correct 66 ms 18192 KB Output is partially correct
4 Partially correct 75 ms 18856 KB Output is partially correct
# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 6484 KB Output is partially correct
2 Correct 43 ms 13104 KB Output is correct
3 Partially correct 66 ms 18192 KB Output is partially correct
4 Partially correct 75 ms 18856 KB Output is partially correct
5 Partially correct 97 ms 18956 KB Output is partially correct
6 Partially correct 107 ms 19756 KB Output is partially correct
7 Partially correct 123 ms 19376 KB Output is partially correct
8 Partially correct 101 ms 20240 KB Output is partially correct
9 Partially correct 81 ms 15876 KB Output is partially correct
10 Partially correct 108 ms 20288 KB Output is partially correct
11 Partially correct 99 ms 20832 KB Output is partially correct
12 Partially correct 89 ms 16016 KB Output is partially correct
13 Partially correct 66 ms 15264 KB Output is partially correct
14 Partially correct 71 ms 15016 KB Output is partially correct
15 Partially correct 93 ms 14608 KB Output is partially correct
16 Partially correct 5 ms 6868 KB Output is partially correct
17 Partially correct 58 ms 14276 KB Output is partially correct
18 Partially correct 56 ms 14208 KB Output is partially correct
19 Partially correct 65 ms 14692 KB Output is partially correct
20 Partially correct 84 ms 17332 KB Output is partially correct
21 Partially correct 92 ms 19248 KB Output is partially correct
22 Partially correct 76 ms 16912 KB Output is partially correct