Submission #1045599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045599		happy_node	Mechanical Doll (IOI18_doll)	C++17	39 / 100	64 ms	57712 KiB

doll

#include "doll.h"

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

const int MX=1e6+5, inf=1e9;

int ch[MX][2], nxt[MX], tot[MX], cnt[MX], par[MX];
bool cond[MX];

int id=1; // switch id

vector<int> G[MX];

void dfs(int v, int dep, int val, int bit, int root) {
        if(dep==1) {
                ch[v][0]= -G[root][val];
                ch[v][1]= -(G[root][val+(1<<bit)]);
                return;
        }

        if(ch[v][0]==inf) {
                ch[v][0]=id++;
        }
        dfs(ch[v][0],dep-1,val,bit+1,root);

        if(ch[v][1]==inf) {
                ch[v][1]=id++;
        }
        dfs(ch[v][1],dep-1,val+(1<<bit),bit+1,root);
}

void create_circuit(int M, std::vector<int> A) { 
        for(int i=0;i<MX;i++) {
                ch[i][0]=ch[i][1]=inf;
                nxt[i]=inf;
        }

        A.push_back(0);       
        int N=A.size();

        vector<int> C(M+1);

        C[0]=A[0];

        for(int i=0;i+1<N;i++) {
                tot[A[i]]++;
                if(nxt[A[i]]==inf) {
                        nxt[A[i]]=id++;
                        C[A[i]]= -nxt[A[i]];
                }
        }

        for(int i=0;i<=M;i++) {
                cnt[i]=tot[i];
                if(C[i]==0) {
                        C[i]=i;
                }
        }

        for(int i=N-2;i>=0;i--) {
                G[A[i]].push_back(A[i+1]);
        }

        for(int i=1;i<=M;i++) {
                if(tot[i]==0) continue;
                int b=0, c=tot[i];
                while(c>0) {
                        b++;
                        c/=2;
                }
                while(G[i].size()<(1<<b)) G[i].push_back(-nxt[i]);
                reverse(G[i].begin(),G[i].end());
                dfs(nxt[i],b,0,0,i);
        }

        vector<int> X,Y;
        for(int i=1;i<id;i++) {
                X.push_back(-ch[i][0]);
                Y.push_back(-ch[i][1]);
        }

        answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:72:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |                 while(G[i].size()<(1<<b)) G[i].push_back(-nxt[i]);
      |                       ~~~~~~~~~~~^~~~~~~

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