제출 #771609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
771609		ttamx	자동 인형 (IOI18_doll)	C++14	47 / 100	89 ms	11040 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
 
using namespace std;
 
void create_circuit(int m,vector<int> a) {
	int n = a.size();
	vector<int> c(m+1);
	vector<int> lg(n+1);
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	vector<int> x,y;
	auto add=[&](int u,int v){
		x.emplace_back(u);
		y.emplace_back(v);
		return -x.size();
	};
	a.push_back(0);
	int sz=n;
	int lv=lg[sz-1]+1;
	vector<int> res;
	int cnt=1<<(lv-1);
	int tar=-(x.size()+(1<<lv)-1);
	int st=(1<<lv)-sz+1;
	vector<int> pos(1<<lv);
	for(int j=0;j<1<<lv;j++){
		for(int k=0;k<lv;k++)if((j>>k)&1)pos[j]+=1<<(lv-k-1);
		pos[j]++;
	}
	for(int k=0;k<cnt;k++){
		int u=pos[k*2],v=pos[k*2+1];
		res.emplace_back(add(u<st?tar:a[u-st+1],v<st?tar:a[v-st+1]));
	}
	while(res.size()>1){
		vector<int> tmp;
		for(int i=0;i<res.size();i+=2)tmp.emplace_back(add(res[i],res[i+1]));
		res=tmp;
	}
	c[0]=a[0];
	for(int i=1;i<=m;i++)c[i]=tar;
	answer(c,x,y);
}

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

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0;i<res.size();i+=2)tmp.emplace_back(add(res[i],res[i+1]));
      |               ~^~~~~~~~~~~

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