Submission #1095846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095846		owoovo	Mechanical Doll (IOI18_doll)	C++17	86 / 100	317 ms	34896 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
#define F first 
#define S second 
using namespace std;
int m,n,a[800010],trans[800010],temp[800010];
int len;
vector<pair<int,pair<int,int>>> ans;
bool need(int l,int r){
	//if(n<=l&&r<len-1)return 0;
	 return 1;
}
bool build(int l,int r,int id){
	if(l+1==r){
		int lc=a[trans[l]],rc=a[trans[r]];
		if(lc==-1&&rc==-1)return 0;
		ans.push_back({-id,{lc,rc}});
		return 1;
	}
	int m=(l+r)>>1;
	int lc=id*2,rc=id*2+1;
	if(build(l,m,id*2)){
	}else{
		lc=1;
	}
	if(build(m+1,r,id*2+1)){
	}else{
		rc=1;
	}
	if(lc==1&&rc==1)return 0;
	ans.push_back({-id,{-lc,-rc}});
	return 1;
}
void create_circuit(int M, std::vector<int> A) {
	vector<int> c,x,y;
	n=A.size();
	m=M;
	len=1;
	c.resize(m+1);
	for(int i=0;i<n;i++)a[i]=A[i];
	for(int i=0;i<=m;i++)c[i]=-1;
	while(len<n+1){
		for(int i=0;i<len;i++)temp[2*i]=trans[i];
		for(int i=0;i<len;i++)temp[2*i+1]=temp[2*i]+len;
		len*=2;
		for(int i=0;i<len;i++)trans[i]=temp[i];
	}
	vector<int> use;
	for(int i=len-n-1;i<len;i++){
		use.push_back(trans[i]);
	}
	sort(use.begin(),use.end());
	map<int,int> nmp;
	for(int i=0;i<use.size();i++){
		nmp.insert({use[i],i});
	}
	for(int i=0;i<len-1;i++){
		if(nmp.count(trans[i])!=0){
			trans[i]=nmp[trans[i]];
		}else{
			trans[i]=n+1;
		}
	}
	a[n]=0;
	a[n+1]=-1;
	build(0,len-1,1);
	sort(ans.begin(),ans.end());
	reverse(ans.begin(),ans.end());
	map<int,int> mp;
	for(int i=0;i<ans.size();i++){
		mp.insert({ans[i].F,i+1});
	}
	for(int i=0;i<ans.size();i++){
		//cout<<ans[i].F<<" "<<ans[i].S.F<<" "<<ans[i].S.S<<"\n";
		if(mp.count(ans[i].S.F)!=0){
			ans[i].S.F=-mp[ans[i].S.F];
		}
		if(mp.count(ans[i].S.S)!=0){
			ans[i].S.S=-mp[ans[i].S.S];
		}
	}
	x.resize(ans.size());
	y.resize(ans.size());
	for(int i=0;i<ans.size();i++){
		x[i]=ans[i].S.F;
		y[i]=ans[i].S.S;
	}
	answer(c,x,y);
	return;
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0;i<use.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~

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