Submission #430186

#	Time	Username	Problem	Language	Result	Execution time	Memory
430186		TLP39	Mechanical Doll (IOI18_doll)	C++14	100 / 100	125 ms	13884 KiB

doll

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

int n;
int a[200010];
int sta=0;
int cur=-1;
int seg[1200040];
int ord[300010];
int cou=0;
vector<int> ss;
int sw(int k)
{
    int ans=0;
    for(int i=0;i<sta;i++)
    {
            if((k>>i)&1) ans+=1<<(sta-1-i);
    }
    return ans;
}

vector<int> toadd;
void build(int v,int st,int ed)
{
    if(ed<(1<<sta)-n)
    {
        seg[v]=-1;
        return;
    }
    if(st==ed)
    {
        seg[v]=a[ord[st]];
        return;
    }
    int mid=(st+ed)>>1;
    seg[v]=cur;
    cur--;
    toadd.push_back(v);
    build(2*v,st,mid);
    build(2*v+1,mid+1,ed);
}

void create_circuit(int M, std::vector<int> A) {
    n=A.size()+1;
    for(int i=0;i<A.size();i++)
    {
        a[i]=A[i];
    }
    a[n-1]=0;
    if(n==2)
    {
        vector<int> c(M+1,0),x,y;
        c[0]=A[0];
        answer(c,x,y);
        return;
    }
    while((1<<sta)<n) sta++;
    for(int i=0;i<(1<<sta);i++) ss.push_back(sw(i));
    for(int i=0;i<ss.size();i++)
    {
        if(ss[i]>=(1<<sta)-n)
        {
            ord[ss[i]]=cou;cou++;
        }
    }
    build(1,0,(1<<sta)-1);
    vector<int> c(M+1,-1),x(-cur-1),y(-cur-1);
    for(int i=0;i<toadd.size();i++)
    {
        x[-1-seg[toadd[i]]]=seg[2*toadd[i]];
        y[-1-seg[toadd[i]]]=seg[2*toadd[i]+1];
    }
    answer(c,x,y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
doll.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<ss.size();i++)
      |                 ~^~~~~~~~~~
doll.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<toadd.size();i++)
      |                 ~^~~~~~~~~~~~~

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