Submission #525707

#	Time	Username	Problem	Language	Result	Execution time	Memory
525707		byunjaewoo	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	97 ms	18640 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#pragma GCC optimize "O3"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll=long long;
 
const int Nmax=200010;
int M, N, A[Nmax];
int cnt, p, vs, siz, out[Nmax], l[2*Nmax], r[2*Nmax];
bool st[2*Nmax];
vector<int> V[Nmax];
 
void DFS_Construct(int curr, int s, int e) {
    if(e-s==1) {
        l[-curr]=r[-curr]=INT_MAX;
        if(s<=siz-vs) l[-curr]=out[p];
        return;
    }
    int m=(s+e)/2;
    if(m<=siz-vs) l[-curr]=out[p];
    else {
        l[-curr]=--cnt;
        DFS_Construct(l[-curr], s, m);
    }
    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;
      	while(siz<V[i].size()) siz*=2;
        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:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |        while(siz<V[i].size()) siz*=2;
      |              ~~~^~~~~~~~~~~~
doll.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j=0; j<V[i].size(); j++) {
      |                      ~^~~~~~~~~~~~

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