Submission #293685

#	Time	Username	Problem	Language	Result	Execution time	Memory
293685		charterla	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	260 ms	140024 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
 
int n;
deque<int> shoes[100005][2];
int stn=1,tree[600005];
bool tag[200005];
 
inline void push_down(int now){
	tree[now<<1]+=tree[now];
	tree[now<<1|1]+=tree[now];
	tree[now]=0;
	return;
}
 
inline void update(int now,int ls,int rs,int lq,int rq,int value){
	if(rq<ls || rs<lq)return;
	if(lq<=ls && rs<=rq){tree[now]+=value;return;}
	push_down(now);
	
	int mid=(ls+rs)>>1;
	update(now<<1,ls,mid,lq,rq,value);
	update(now<<1|1,mid+1,rs,lq,rq,value);
	return;
}
 
inline int search(int now,int ls,int rs,int to){
	//cout<<now<<" "<<ls<<" "<<rs<<" "<<to<<endl; 
	if(ls==to && rs==to)return tree[now];
	push_down(now);
	
	int mid=(ls+rs)>>1;
	if(to<=mid)return search(now<<1,ls,mid,to);
	else return search(now<<1|1,mid+1,rs,to);
}
 
inline int value(int now){return now<0?now*-1:now;}
 
inline int answer(int a,int b,bool way){
	int ta=a+search(1,1,stn,a+1),tb=b+search(1,1,stn,b+1);//cout<<ta<<" "<<tb<<endl;
	if(way)return tb-ta;else return tb-ta-1;
}

inline void check(){
	for(int i=1;i<=n>>1;i++){
		cout<<i<<": ";
		for(int j=0;j<2;j++){
			for(int k=0;k<shoes[i][j].size();k++)cout<<shoes[i][j][k]<<" ";cout<<"; ";
		}cout<<endl;
	}cout<<endl;
	return;
}
 
long long count_swaps(vector<int> s) {
	n=s.size();while(stn<n)stn<<=1;
	for(int i=0;i<n;i++)shoes[value(s[i])][s[i]<0].push_back(i);//check();
	
	long long ans=0;
	for(int a=0,b;a<n;a++){
		if(tag[a])continue;
		
		b=shoes[value(s[a])][s[a]>=0].front();//cout<<a<<" "<<b<<endl;
		shoes[value(s[a])][0].pop_front();shoes[value(s[a])][1].pop_front();
		tag[a]=tag[b]=true;//cout<<a<<","<<b<<" ";
		ans+=(long long)answer(a,b,s[a]>0);//cout<<ans<<endl;check();
		
		update(1,1,stn,a+1,b+1,1);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'void check()':
shoes.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(int k=0;k<shoes[i][j].size();k++)cout<<shoes[i][j][k]<<" ";cout<<"; ";
      |                ~^~~~~~~~~~~~~~~~~~~
shoes.cpp:51:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |    for(int k=0;k<shoes[i][j].size();k++)cout<<shoes[i][j][k]<<" ";cout<<"; ";
      |    ^~~
shoes.cpp:51:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |    for(int k=0;k<shoes[i][j].size();k++)cout<<shoes[i][j][k]<<" ";cout<<"; ";
      |                                                                   ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15