Submission #106723

#	Time	Username	Problem	Language	Result	Execution time	Memory
106723		ppnxblstr	Mechanical Doll (IOI18_doll)	C++14	53 / 100	323 ms	42436 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int swcnt;
int newswitch(){
    return ++swcnt;
}
class fakeswitch{
public:
    fakeswitch* l;
    fakeswitch* r;
    bool t;
    int val;
    fakeswitch(int x = -1) : l(nullptr), r(nullptr), val(x), t(false) {}
};
fakeswitch* buildfakesw(int lv){
    if(lv == 0) return new fakeswitch(0);
    fakeswitch* cur = new fakeswitch();
    cur->l = buildfakesw(lv-1);
    cur->r = buildfakesw(lv-1);
    return cur;
}
void trav(fakeswitch* cur, int key){
    if(cur->l == nullptr && cur->r == nullptr){
        cur->val = key;
        return;
    }
    if(cur->t) trav(cur->r, key);
    else trav(cur->l, key);
    cur->t = !cur->t;
}
int realize(fakeswitch* cur, vector<int>& X, vector<int>& Y, const vector<int>& v, int root = 0){
    if(cur->val >= 0){
        if(v[cur->val] == -1) return root;
        return v[cur->val];
    }
    int c = -newswitch();
    if(root == 0) root = c;
    X[-1-c] = realize(cur->l, X, Y, v, root);
    Y[-1-c] = realize(cur->r, X, Y, v, root);
    return c;
}
void debug(fakeswitch* sw){
    if(sw == nullptr) return;
    debug(sw->l);
    printf(" %d",sw->val);
    debug(sw->r);
}
int count(fakeswitch* sw){
    if(sw == nullptr || sw->val >= 0) return 0;
    return count(sw->l) + count(sw->r) + 1;
}
vector<int> pot = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144};
void buildsw(vector<int>& C, vector<int>& X, vector<int>& Y, int& trig, vector<int> ord){
    int z = ord.size();
    int idx = lower_bound(pot.begin(), pot.end(), z) - pot.begin();
    fakeswitch* root = buildfakesw(idx);
    int k = ord.back();
    ord.pop_back();
    while(ord.size() < pot[idx]-1) ord.push_back(-1);
    ord.push_back(k);
    for(int i = 0; i < pot[idx]; i++) trav(root, i);
    C[trig] = realize(root, X, Y, ord);
}
vector<int> bckt[200005];
void create_circuit(int M, vector<int> A) {
  int N = A.size();
  bckt[0].push_back(A[0]);
  for(int i = 1; i < N; i++){
      bckt[A[i-1]].push_back(A[i]);
  }
  bckt[A[N-1]].push_back(0);
  vector<int> C;
  C.resize(M+1);
  vector<int> X, Y;
  X.resize(400005, 1e9);
  Y.resize(400005, 1e9);
  for(int i = 0; i <= M; i++){
      if(bckt[i].empty()) continue;
      auto buf = bckt[i];
      buildsw(C,X,Y,i,buf);
  }
  while(!X.empty() && X.back() == 1e9) X.pop_back();
  while(!Y.empty() && Y.back() == 1e9) Y.pop_back();
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In constructor 'fakeswitch::fakeswitch(int)':
doll.cpp:14:9: warning: 'fakeswitch::val' will be initialized after [-Wreorder]
   14 |     int val;
      |         ^~~
doll.cpp:13:10: warning:   'bool fakeswitch::t' [-Wreorder]
   13 |     bool t;
      |          ^
doll.cpp:15:5: warning:   when initialized here [-Wreorder]
   15 |     fakeswitch(int x = -1) : l(nullptr), r(nullptr), val(x), t(false) {}
      |     ^~~~~~~~~~
doll.cpp: In function 'void buildsw(std::vector<int>&, std::vector<int>&, std::vector<int>&, int&, std::vector<int>)':
doll.cpp:61:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   61 |     while(ord.size() < pot[idx]-1) ord.push_back(-1);
      |           ~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56