Submission #525677

#	Time	Username	Problem	Language	Result	Execution time	Memory
525677		byunjaewoo	Mechanical Doll (IOI18_doll)	C++17	16 / 100	1057 ms	44460 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;
 
inline 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 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++) {
            for(int curr=out[i]; ; ) {
                st[curr]^=1;
                if(!st[curr]) {
                    if(r[curr]==INT_MAX) {
                        r[curr]=V[i][j];
                        break;
                    }
                    curr=r[curr];
                }
                else {
                    if(l[curr]==INT_MAX) {
                        l[curr]=V[i][j];
                        break;
                    }
                    curr=l[curr];
                }
            }
        }
    }
    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:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int j=0; j<V[i].size(); 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