Submission #1045112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045112		n1k	Mechanical Doll (IOI18_doll)	C++17	100 / 100	91 ms	14180 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
//#include "debug.cpp"

#define debug(...) 0

using namespace std;

vector<int> x, y, c, state, order;
vector<array<int, 2>> in;
int t = 0;

int tree(vector<int> nodes){
    // nodes.size() must be a power of 2
    // returns id of exit node
    while(nodes.size()>1){
        vector<int> nnodes;
        for(int i=0; i<nodes.size(); i+=2){
            x.push_back(nodes[i]);
            y.push_back(nodes[i+1]);
            state.push_back(0);

            nnodes.push_back(-x.size());
            if(nodes[i]>=0){
                in[nodes[i]]={-int(x.size()), 0};
            }
            if(nodes[i+1]>=0){
                in[nodes[i+1]]={-int(x.size()), 1};
            }
        }
        swap(nodes, nnodes);
    }
    return nodes.front();
}

void sim(int u){
    if(u>=0){
        if(order[u]!=-1){
            return;
        }
        order[u]=t++;
        sim(c[u]);
    }else{
        u = -u-1;
        if(state[u]==0){
            state[u]^=1;
            sim(x[u]);
        }else{
            state[u]^=1;
            sim(y[u]);
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
    int n = A.size(), now = 1;
    vector<int> roots(20);
    in.assign(n+1, {});
    for(int i=0; i<20; i++){
        if(n&(1<<i)){
            vector<int> nodes(1<<i);
            iota(nodes.begin(), nodes.end(), now);
            roots[i]=tree(nodes);
            now += 1<<i;
        }
    }


    // make switcher
    int len = log2(n) + 1;
    int start = -x.size()-1;
    for(int i=0; i<len; i++){
        if(roots[len - i - 1]){
            x.push_back(roots[len - i - 1]);
            y.push_back(-x.size() - 1);
            state.push_back(0);
            if(roots[len - i - 1]>=0){
                in[roots[len - i - 1]] = {-int(x.size()), 0};
            }
        }else{
            x.push_back(start);
            y.push_back(-x.size() - 1);
            state.push_back(0);
     
        }
    }
    y.back() = 0;

    c.assign(n+1, start);
    order.assign(n+1, -1);

    sim(start);

    c.assign(M+1, start);
    c[0]=start;

    vector<array<int, 2>> rev(n+1);
    for(int i=0; i<order.size(); i++){
        rev[order[i]] = in[i];
    }
    debug(order);
    debug(c);
    debug(x);
    debug(y);
    debug(in);
    debug(rev);

    for(int i=0; i<n; i++){
        auto [module, side] = rev[i];
        module = -module - 1;
        if(side==0){
            x[module] = A[i];
        }else{
            y[module] = A[i];
        }
    }

    debug(c);
    debug(x);
    debug(y);

    answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'int tree(std::vector<int>)':
doll.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i=0; i<nodes.size(); i+=2){
      |                      ~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0; i<order.size(); i++){
      |                  ~^~~~~~~~~~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:101:5: note: in expansion of macro 'debug'
  101 |     debug(order);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:102:5: note: in expansion of macro 'debug'
  102 |     debug(c);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:103:5: note: in expansion of macro 'debug'
  103 |     debug(x);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:104:5: note: in expansion of macro 'debug'
  104 |     debug(y);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:105:5: note: in expansion of macro 'debug'
  105 |     debug(in);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:106:5: note: in expansion of macro 'debug'
  106 |     debug(rev);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:118:5: note: in expansion of macro 'debug'
  118 |     debug(c);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:119:5: note: in expansion of macro 'debug'
  119 |     debug(x);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:120:5: note: in expansion of macro 'debug'
  120 |     debug(y);
      |     ^~~~~

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