Submission #1364539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1364539		mariza	Mechanical Doll (IOI18_doll)	C++20	37 / 100	50 ms	10392 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void create_circuit(int m, vector<int> a) {
    ll n=a.size()+1;

    ll k=1;
    while(k<n){
        k*=2;
    }

    while(a.size()<k-1) a.push_back(-1);
    a.push_back(0);
    n=a.size();

    vector<int> c(m+1,-1);

    vector<int> s0(1,a[0]), s1(1,a[1]);
    ll s=1;
    vector<int> x(1,0);
    for(ll i=2; i<n; i++){
        ll curr=-1, prev=-1;
        while(curr<0){
            if(x[-curr-1]==0){
                x[-curr-1]=1;
                prev=curr;
                curr=s0[-curr-1];
            }
            else{
                x[-curr-1]=0;
                prev=curr;
                curr=s1[-curr-1];
            }
        }

        s++;
        if(x[-prev-1]==1) s0[-prev-1]=-s;
        else s1[-prev-1]=-s;
        s0.push_back(curr);
        s1.push_back(a[i]);
        x.push_back(0);
    }

    // for(ll i=0; i<s; i++){
    //     if(s0[i]<0 && s1[i]>=0){
    //         s0.push_back(s1[i]);
    //         s1.back()=-1;
    //         s1.push_back(0);
    //         s1[i]=-s0.size();
    //     }
    // }

    answer(c,s0,s1);
}

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