Submission #771598

#	Time	Username	Problem	Language	Result	Execution time	Memory
771598		ttamx	Mechanical Doll (IOI18_doll)	C++14	37 / 100	88 ms	11324 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.emplace_back(0);
	int sz=n+1;
	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],v<st?tar:a[v-st]));
	}
	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;
	}
	for(auto &x:c)x=tar;
	answer(c,x,y);
}

Compilation message (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: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56