Submission #525671

#	Time	Username	Problem	Language	Result	Execution time	Memory
525671		byunjaewoo	Mechanical Doll (IOI18_doll)	C++17	16 / 100	860 ms	262148 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
const int Nmax=200010;
int M, N, A[Nmax];
int cnt, p, vs, siz, out[Nmax];
vector<int> V[Nmax];
unordered_map<int, int> l, r;
unordered_map<int, bool> st;
 
void DFS_Construct(int curr, int s, int e) {
    if(e-s==1) {
        l[curr]=r[curr]=INT_MAX;
        if(s<=siz-vs) r[curr]=out[p];
        return;
    }
    int m=(s+e)/2;
    l[curr]=--cnt;
    DFS_Construct(l[curr], s, m);
    if(m<=siz-vs) r[curr]=out[p];
    else {
        r[curr]=--cnt;
        DFS_Construct(r[curr], m+1, e);
    }
}
 
void DFS_Connect(int curr, int k) {
    st[curr]^=1;
    if(!st[curr]) {
        if(r[curr]==INT_MAX) {
            r[curr]=V[p][k];
            return;
        }
        DFS_Connect(r[curr], k);
    }
    else {
        if(l[curr]==INT_MAX) {
            l[curr]=V[p][k];
            return;
        }
        DFS_Connect(l[curr], k);
    }
}
 
void create_circuit(int M, vector<int> A) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    N=A.size();
    V[0].push_back(A[0]);
    for(int i=0; i<N-1; i++) V[A[i]].push_back(A[i+1]);
  	V[A[N-1]].push_back(0);
    for(int i=0; i<=M; i++) if(V[i].size()) {
        if(V[i].size()==1) {
            out[i]=V[i][0];
            continue;
        }
        p=i, vs=V[i].size(), siz=(1<<(32-__builtin_clz(V[i].size()-1)));
        out[i]=--cnt;
        DFS_Construct(out[i], 1, siz);
        for(int j=0; j<V[i].size(); j++) DFS_Connect(out[i], j);
    }
    vector<int> C, X, Y;
    for(int i=0; i<=M; i++) C.push_back(out[i]);
    for(int i=-1; i>=cnt; i--) {
        X.push_back(l[i]); Y.push_back(r[i]);
    }
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j=0; j<V[i].size(); j++) DFS_Connect(out[i], j);
      |                      ~^~~~~~~~~~~~

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