제출 #430166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
430166		TLP39	자동 인형 (IOI18_doll)	C++14	12 / 100	76 ms	9892 KiB

doll

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

int n;
int a[200010];
int sta=0;
int cur=-1;
int seg[800040];
int ord[200010];
int cou=0;
vector<int> ss;
int sw(int k)
{
    int ans=0;
    for(int i=0;i<sta;i++)
    {
            if((k>>i)&1) ans+=1<<(sta-1-i);
    }
    return ans;
}

vector<int> toadd;
void build(int v,int st,int ed)
{
    if(ed<(1<<sta)-n)
    {
        seg[v]=-1;
        return;
    }
    if(st==ed)
    {
        seg[v]=a[ord[st]];
        return;
    }
    int mid=(st+ed)>>1;
    seg[v]=cur;
    cur--;
    toadd.push_back(v);
    build(2*v,st,mid);
    build(2*v+1,mid+1,ed);
}

void create_circuit(int M, std::vector<int> A) {
    n=A.size()+1;
    for(int i=0;i<A.size();i++)
    {
        a[i]=A[i];
    }
    a[n-1]=0;
    if(n==2)
    {
        vector<int> c(M+1,0),x,y;
        c[0]=A[0];
        answer(c,x,y);
        return;
    }
    while((1<<sta)<n) sta++;
    for(int i=0;i<(1<<sta);i++) ss.push_back(sw(i));
    for(int i=0;i<ss.size();i++)
    {
        if(ss[i]>=(1<<sta)-n)
        {
            ord[ss[i]]=cou;cou++;
        }
    }
    build(1,0,(1<<sta)-1);
    vector<int> c(M+1,-1),x(-cur-1),y(-cur-1);
    for(int i=0;i<toadd.size();i++)
    {
        x[-1-seg[toadd[i]]]=seg[2*toadd[i]];
        y[-1-seg[toadd[i]]]=seg[2*toadd[i]+1];
    }
    answer(c,x,y);
}

컴파일 시 표준 에러 (stderr) 메시지

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

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