Submission #1163619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163619		irmuun	Mechanical Doll (IOI18_doll)	C++20	37 / 100	109 ms	14432 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

void create_circuit(int M,vector<int>A) {
    int N=A.size();
    vector<int>C(M+1);
    fill(all(C),-1);
    vector<int>X(4*N,0),Y(4*N,0);
    int len=0;
    vector<int>row={1};
    while(row.size()*2<=N){
        vector<int>vec;
        for(int i:row){
            X[i]=-(2*i);
            Y[i]=-(2*i+1);
            vec.pb(2*i);
            vec.pb(2*i+1);
        }
        row=vec;
    }
    for(int i:row){
        X[i]=-(2*i);
        Y[i]=-(2*i+1);
    }
    vector<int>ord;
    vector<bool>dir(2*X.size(),true);
    int cur=1;
    while(ord.size()<2*row.size()){
        if(X[cur]==0){
            ord.pb(cur);
            cur=1;
            continue;
        }
        if(dir[cur]){
            dir[cur]=false;
            cur=-X[cur];
        }
        else{
            dir[cur]=true;
            cur=-Y[cur];
        }
    }
    for(int i=0;i<N;i++){
        if(ord[i]%2==0) X[ord[i]/2]=A[i];
        else Y[ord[i]/2]=A[i];
    }
    for(int i=N;i<ord.size();i++){
        if(ord[i]%2==0) X[ord[i]/2]=-1;
        else Y[ord[i]/2]=-1;
    }
    Y[ord.size()-1]=0;
    X.resize(row.size()*2);
    Y.resize(row.size()*2);
    X.erase(X.begin());
    Y.erase(Y.begin());
    answer(C,X,Y);
}

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