Submission #571557

#	Time	Username	Problem	Language	Result	Execution time	Memory
571557		Hanksburger	Mechanical Doll (IOI18_doll)	C++17	69.55 / 100	85 ms	14936 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> v[100005], c, x, y;
int b[400005];
void recur(int l, int r, int p, bool q)
{
    if (b[r]<0 || l==r)
    {
        if (q)
            y[p-1]=b[r];
        else
            x[p-1]=b[r];
        return;
    }
    x.push_back(0);
    y.push_back(0);
    int num=x.size();
    if (q)
        y[p-1]=-num;
    else
        x[p-1]=-num;
    int mid=(l+r)/2;
    recur(l, mid, num, 0);
    recur(mid+1, r, num, 1);
}
void create_circuit(int m, vector<int> a)
{
    for (int i=0; i<=a.size()-2; i++)
        v[a[i]].push_back(a[i+1]);
    v[a[a.size()-1]].push_back(0);
    v[0].push_back(a[0]);
    for (int i=0; i<=m; i++)
    {
        if (v[i].empty())
        {
            c.push_back(0);
            continue;
        }
        if (v[i].size()==1)
        {
            c.push_back(v[i][0]);
            continue;
        }
        x.push_back(0);
        y.push_back(0);
        int num=x.size();
        int sz=v[i].size();
        int loog=log2(sz-0.5)+1;
        int power=(1<<loog);
        int cnt=0;
        c.push_back(-num);
        for (int j=0; j<power; j++)
        {
            int cur=0;
            for (int k=0; k<loog; k++)
                if (j&(1<<k))
                    cur+=(1<<(loog-k-1));
            if (cur>=power-sz)
            {
                b[cur]=v[i][cnt];
                cnt++;
            }
            else
                b[cur]=-num;
        }
        recur(0, power/2-1, num, 0);
        recur(power/2, power-1, num, 1);
    }
    answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:29:20: 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<=a.size()-2; i++)
      |                   ~^~~~~~~~~~~~

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