Submission #612012

#	Time	Username	Problem	Language	Result	Execution time	Memory
612012		M_W	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	99 ms	17876 KiB

doll

#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<1500000> 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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 41.5530038336 / 56