Submission #714137

#	Time	Username	Problem	Language	Result	Execution time	Memory
714137		victor_gao	Mechanical Doll (IOI18_doll)	C++17	100 / 100	131 ms	15088 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>ans1,ans2,c,arr;
int n,m,now=0,vis[400015];
pii seg[400015];
int build(int l,int r,int root,int out){
    if (l==r)
        return -root;
    int mid=(l+r)>>1,use=--now;
    use=abs(use);
    if (out<(mid-l+1)){
        seg[use].x=build(l,mid,root,out);
        seg[use].y=build(mid+1,r,root,0);
    }
    else {
        out-=(mid-l+1);
        seg[use].x=root;
        seg[use].y=build(mid+1,r,root,out);
    }
    return use;
}
void dfs(int i,int order,int root){
    if (order==arr.size()) return;
    if (!vis[i]){
        vis[i]^=1;
        if (seg[i].x==-root)
            ans1[i]=arr[order++];
        else ans1[i]=-seg[i].x;
        dfs(abs(seg[i].x),order,root);
    }
    else {
        vis[i]^=1;
        if (seg[i].y==-root)
            ans2[i]=arr[order++];
        else ans2[i]=-seg[i].y;
        dfs(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(); arr=A;
    c.resize(m+1,-1);
    int p=__lg(n-1)+1;
    build(0,(1LL<<p)-1,1,(1LL<<p)-n);
    dfs(1,0,1);
    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 7
1 1 1 1 1 1 1 1 
./rand
./doll
*/

Compilation message (stderr)

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

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