Submission #461395

#	Time	Username	Problem	Language	Result	Execution time	Memory
461395		urd05	Mechanical Doll (IOI18_doll)	C++17	53 / 100	194 ms	29728 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> v;
vector<int> x;
vector<int> y;
vector<int> nt[100001];
int now=-1;
 
void func(int st,vector<int> vec) {
    if (vec.empty()) {
        return;
    }
    if (vec.size()==2) {
        x[-st-1]=vec[0];
        y[-st-1]=vec[1];
        return;
    }
    int nt1,nt2;
    x[-st-1]=now;
    nt1=now;
    now--;
    y[-st-1]=now;
    nt2=now;
    now--;
    vector<int> v1;
    vector<int> v2;
    for(int i=0;i<vec.size();i++) {
        if (i%2==0) {
            v1.push_back(vec[i]);
        }
        else {
            v2.push_back(vec[i]);
        }
    }
    func(nt1,v1);
    func(nt2,v2);
}
 
void create_circuit(int m,vector<int> a) {
    int n=a.size();
    v.resize(m+1);
    x.resize(2000000);
    y.resize(2000000);
    nt[0].push_back(a[0]);
    for(int i=1;i<n;i++) {
        nt[a[i-1]].push_back(a[i]);
    }
    nt[a[n-1]].push_back(0);
    for(int i=0;i<=m;i++) {
        if (nt[i].empty()) {
            v[i]=0;
            continue;
        }
        if (nt[i].size()==1) {
            v[i]=nt[i][0];
            continue;
        }
        v[i]=now;
        now--;
        int sz=nt[i].size();
        int newsz=1;
        while (newsz<sz) {
            newsz*=2;
        }
        nt[i].resize(newsz);
        for(int j=newsz-1;j>=0;j--) {
            if (j>=newsz-sz) {
                nt[i][j]=nt[i][j-newsz+sz];
            }
            else {
                nt[i][j]=v[i];
            }
        }
        func(v[i],nt[i]);
    }
    x.resize(-now-1);
    y.resize(-now-1);
    assert(now>=-400001);
    answer(v,x,y);
}

Compilation message (stderr)

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

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