Submission #853894

#	Time	Username	Problem	Language	Result	Execution time	Memory
853894		abcvuitunggio	Mechanical Doll (IOI18_doll)	C++17	100 / 100	85 ms	15312 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
vector <int> c,x,y,ve,o;
int n,sz=1,id,pos[1000001];
int f(int l, int r){
    if (ve[l]==-1&&ve[r]==-1)
        return INF;
    if (l==r)
        return ve[l];
    int mid=(l+r)>>1,left=f(l,mid),right=f(mid+1,r);
    x.push_back(left);
    y.push_back(right);
    id--;
    return id;
}
vector <int> rearrange(int l, int r){
    if (l==r)
        return {l};
    int mid=(l+r)>>1;
    auto vl=rearrange(l,mid);
    auto vr=rearrange(mid+1,r);
    vector <int> ve;
    for (int i=0;i<vl.size();i++){
        ve.push_back(vl[i]);
        ve.push_back(vr[i]);
    }
    return ve;
}
void create_circuit(int M, vector <int> A){
    A.push_back(0);
    n=A.size();
    while (sz<n)
        sz*=2;
    ve=rearrange(0,sz-1);
    for (int i=0;i<sz;i++)
        pos[ve[i]]=i;
    for (int i=0;i<sz-n;i++)
        ve[i]=-1;
    int j=-1;
    for (int i:A){
        j++;
        while (pos[j]<sz-n)
            j++;
        ve[pos[j]]=i;
    }
    f(0,sz-1);
    for (int &i:x)
        if (i==INF)
            i=id;
    for (int i=0;i<=M;i++)
        c.push_back(id);
    answer(c,x,y);
}

Compilation message (stderr)

doll.cpp: In function 'std::vector<int> rearrange(int, int)':
doll.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i=0;i<vl.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