Submission #1095799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095799		owoovo	Mechanical Doll (IOI18_doll)	C++17	37 / 100	170 ms	30988 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;
}
void build(int l,int r,int id){
	if(l+1==r){
		ans.push_back({-id,{a[trans[l]],a[trans[r]]}});
		return;
	}
	int m=(l+r)>>1;
	int lc=id*2,rc=id*2+1;
	if(need(l,m)){
		build(l,m,id*2);
	}else{
		lc=1;
	}
	if(need(m+1,r)){
		build(m+1,r,id*2+1);
	}else{
		rc=1;
	}
	ans.push_back({-id,{-lc,-rc}});
	return;
}
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];
	}
	for(int i=n;i<len-1;i++)a[i]=-1;
	a[len-1]=0;
	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:53: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]
   53 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:56: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]
   56 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~
doll.cpp:67: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]
   67 |  for(int i=0;i<ans.size();i++){
      |              ~^~~~~~~~~~~

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