Submission #1263534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263534		vivkostov	Mechanical Doll (IOI18_doll)	C++20	0 / 100	0 ms	324 KiB

doll

//#pragma once
//#include "grader.cpp"
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
int n,m,a[200005],x[1000005],y[1000005],step;
vector<int>c,X,Y;
void create(int l,int r,int h,int st,int level)
{
    if(l+1>=r)
    {
        if(st>m-2)x[h]=-1;
        else x[h]=a[st+2];
        st+=(1<<level);
        if(st==n-1)y[h]=0;
        else if(st>m-2)y[h]=-1;
        else y[h]=a[st+2];
        return;
    }
    int mid=(l+r)/2;
    create(l,mid,h*2,st,level+1);
    create(mid+1,r,h*2+1,st+(1<<level),level+1);
    x[h]=-h*2;
    y[h]=-(h*2+1);
}
void check(int l,int r,int h)
{
    X.push_back(x[h]);
    Y.push_back(y[h]);
    //cout<<x[h]<<" "<<y[h]<<" "<<l<<" "<<r<<endl;
    if(l+1>=r)return;
    int mid=(l+r)/2;
    check(l,mid,h*2);
    check(mid+1,r,h*2+1);
}
void create_circuit(int M, std::vector<int> A)
{
    n=A.size();
    m=M;
    for(int i=1; i<=n; i++)
    {
        a[i]=A[i-1];
    }
    if(n==1)
    {
        c.push_back(a[1]);
        for(int i=1; i<=m; i++)
        {
            c.push_back(0);
        }
        answer(c,X,Y);
        return;
    }
    while((1<<step)<n)step++;
    n=(1<<step);
    //cout<<n<<endl;
    create(1,n,1,0,0);
    c.push_back(a[1]);
    for(int i=1; i<=m; i++)
    {
        c.push_back(-1);
    }
    check(1,n,1);
    answer(c,X,Y);
}

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