Submission #714128

#	Time	Username	Problem	Language	Result	Execution time	Memory
714128		victor_gao	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	110 ms	26968 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int>to[200015],g[200015];
vector<int>ans1,ans2,c;
int n,m,now=0,vis[400015];
pii seg[400015];
int build(int num,int l,int r,int root,int out){
    if (l==r){
        if (out) return root;
        return -root;
    }
    int mid=(l+r)>>1,use=--now;
    use=abs(use);
    if (out<=(mid-l+1)){
        seg[use].x=build(num,l,mid,root,out);
        seg[use].y=build(num,mid+1,r,root,0);
    }
    else {
        out-=(mid-l+1);
        seg[use].x=root;
        seg[use].y=build(num,mid+1,r,root,out);
    }
    return use;
}
void dfs(int num,int i,int order,int root){
    if (order==g[num].size()) return;
    if (!vis[i]){
        vis[i]^=1;
        if (seg[i].x==-root)
            ans1[i]=g[num][order++];
        else ans1[i]=-seg[i].x;
        dfs(num,abs(seg[i].x),order,root);
    }
    else {
        vis[i]^=1;
        if (seg[i].y==-root)
            ans2[i]=g[num][order++];
        else ans2[i]=-seg[i].y;
        dfs(num,abs(seg[i].y),order,root);
    }
    return;
}
void create_circuit(int M, std::vector<int> A) {
    m=M;
    ans1.resize(400000); ans2.resize(400000);
    A.push_back(0);
    n = A.size();
    for (int i=0;i<n-1;i++){
        g[A[i]].push_back(A[i+1]);
    }
    c.resize(m+1);
    int now_root=0;
    for (int i=0;i<=m;i++){
        if (g[i].empty()) c[i]=0;
        else if (g[i].size()==1) c[i]=g[i][0];
        else {
            int p=__lg((int)(g[i].size()-1))+1;
            now_root=abs(now)+1;
            c[i]=-now_root;
            build(i,0,(1LL<<p)-1,now_root,(1LL<<p)-g[i].size());
            dfs(i,now_root,0,now_root);
        }
    }
    c[0]=A[0];
    now=abs(now);
    vector<int>X,Y;
    for (int i=1;i<=now;i++){
        X.push_back(ans1[i]);
    }
    for (int i=1;i<=now;i++){
        Y.push_back(ans2[i]);
    }
    answer(c, X, Y);
}
/*
2 16
1 2 2 1 2 2 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 2 1
4 5
1 2 1 3 1
./rand
./doll
*/

Compilation message (stderr)

doll.cpp: In function 'void dfs(int, int, int, int)':
doll.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     if (order==g[num].size()) return;
      |         ~~~~~^~~~~~~~~~~~~~~

• 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