제출 #571557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571557		Hanksburger	자동 인형 (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);
}

컴파일 시 표준 에러 (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++)
      |                   ~^~~~~~~~~~~~

• 서브태스크 1: 0 / 2
• 서브태스크 2: 0 / 4
• 서브태스크 3: 0 / 10
• 서브태스크 4: 10 / 10
• 서브태스크 5: 18 / 18
• 서브태스크 6: 41.5530038336 / 56