Submission #406000

#	Time	Username	Problem	Language	Result	Execution time	Memory
406000		urd05	Mechanical Doll (IOI18_doll)	C++14	0 / 100	29 ms	12000 KiB

doll

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

int n;
vector<int> nt[100000];
int now=-1;
vector<int> x;
vector<int> y;
vector<int> arr;

void func(int v,int ind,int l,int r,int bit) {
    if (r<l+(1<<bit)) {
        if (l==r) {
            x[-ind-1]=ind;
            y[-ind-1]=nt[v][l];
        }
        else {
            x[-ind-1]=ind;
            y[-ind-1]=now--;
            func(v,now+1,l,r,bit-1);
        }
        return;
    }
    if (bit==0) {
        x[-ind-1]=nt[v][l];
        y[-ind-1]=nt[v][r];
        return;
    }
    x[-ind-1]=now--;
    func(v,now+1,l,l+(1<<bit)-1,bit-1);
    y[-ind-1]=now--;
    func(v,now+1,l+(1<<bit),r,bit-1);
}

void create_circuit(int m,vector<int> a) {
    n=a.size();
    arr.resize(m+1);
    arr[0]=a[0];
    x.resize(200000);
    y.resize(200000);
    for(int i=0;i<n-1;i++) {
        nt[a[i]].push_back(a[i+1]);
    }
    nt[a[n-1]].push_back(0);
    for(int i=1;i<=m;i++) {
        int bit=0;
        while ((1<<(bit+1))<nt[i].size()) {
            bit++;
        }
        if (nt[i].empty()) {
            continue;
        }
        if (nt[i].size()==1) {
            arr[i]=nt[i][0];
            continue;
        }
        arr[i]=now;
        now--;
        func(i,now+1,0,nt[i].size()-1,bit);
    }
    x.resize(-now-1);
    y.resize(-now-1);
    answer(arr,x,y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:48:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while ((1<<(bit+1))<nt[i].size()) {
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~

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