Submission #1263536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263536		vivkostov	Mechanical Doll (IOI18_doll)	C++20	10 / 100	40 ms	11468 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,on;
vector<int>c,X,Y;
void create(int l,int r,int h,int st,int level)
{
    if(l+1>=r)
    {
        if(st>on-2)x[h]=-1;
        else x[h]=a[st+2];
        st+=(1<<level);
        if(st==n-1)y[h]=0;
        else if(st>on-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)
{
    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();
    on=n;
    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);
    for(int i=1;i<=n*4;i++)
    {
        if(x[i])
        {
            X.push_back(x[i]);
            Y.push_back(y[i]);
        }
    }
    answer(c,X,Y);
}

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