Submission #126552

#	Time	Username	Problem	Language	Result	Execution time	Memory
126552		HungAnhGoldIBO2020	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	2 ms	376 KiB

joi2019_ho_t4

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
const int N=2e5+2;
pair<int,int> coor[N];
vector<int> lis,lis1;
bool used[N],wow[N>>1][2];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j;
	long long ans=0,ans1=0;
	cin>>n;
	for(i=1;i<=2*n;i++){
		cin>>coor[i].first>>coor[i].second;
	}
	sort(coor+1,coor+1+2*n);
	j=1;
	for(i=1;i<=n;i++){
		while(j<=2*n&&coor[j].first<=i){
			if(coor[j].second>=2){
				lis1.push_back(j);
			}
			else{
				lis.push_back(j);
			}
			j++;
		}
		if(lis.size()){
			ans+=abs(coor[lis.back()].first-i)+abs(coor[lis.back()].second-1);
			used[lis.back()]=true;
			lis.pop_back();
		}
		else{
			wow[i][0]=true;
		}
		if(lis1.size()){
			ans+=abs(coor[lis1.back()].first-i)+abs(coor[lis1.back()].second-2);
			used[lis1.back()]=true;
			lis1.pop_back();
		}
		else{
			wow[i][1]=true;
		}
	}
	lis.clear();
	lis1.clear();
	j=2*n;
	for(i=n;i>=1;i--){
		while(j&&coor[j].first>=i){
			if(!used[j]){
				if(coor[j].second>=2){
					lis1.push_back(j);
				}
				else{
					lis.push_back(j);
				}
			}
			j--;
		}
		if(!wow[i][0]&&!wow[i][1]){
			continue;
		}
		if(wow[i][0]){
			if(lis.size()){
				ans+=abs(coor[lis.back()].first-i)+abs(coor[lis.back()].second-1);
				used[lis.back()]=true;
				lis.pop_back();
				wow[i][0]=false;
			}
		}
		if(wow[i][1]){
			if(lis1.size()){
				ans+=abs(coor[lis1.back()].first-i)+abs(coor[lis1.back()].second-2);
				used[lis1.back()]=true;
				lis1.pop_back();
				wow[i][1]=false;
			}
	 	}
		if(wow[i][0]){
			if(lis1.size()){
				ans+=abs(coor[lis1.back()].first-i)+abs(coor[lis1.back()].second-1);
				used[lis1.back()]=true;
				lis1.pop_back();
				wow[i][0]=false;
			}
		}
		if(wow[i][1]){
			if(lis.size()){
				ans+=abs(coor[lis.back()].first-i)+abs(coor[lis.back()].second-2);
				used[lis.back()]=true;
				lis.pop_back();
				wow[i][1]=false;
			}
		}
	}
	lis.clear();
	lis1.clear();
	j=1;
	for(i=1;i<=n;i++){
		while(j<=2*n&&coor[j].first<=i){
			if(!used[j]){
				if(coor[j].second>=2){
					lis1.push_back(j);
				}
				else{
					lis.push_back(j);
				}
			}	
			j++;
		}
		if(wow[i][0]){
			ans+=abs(i-coor[lis1.back()].first)+abs(1-coor[lis1.back()].second);
			lis1.pop_back();
		}
		if(wow[i][1]){
			ans+=abs(i-coor[lis.back()].first)+abs(2-coor[lis.back()].second);
			lis.pop_back();
		}
	}
	//cout<<ans;
	for(i=1;i<=2*n;i++){
		wow[(i+1)>>1][(i+1)&1]=false;
		used[i]=false;
	}
	j=1;
	bool cac,cac1;
	for(i=1;i<=n;i++){
		while(j<=2*n&&coor[j].first<=i){
			if(coor[j].second>=2){
				lis1.push_back(j);
			}
			else{
				lis.push_back(j);
			}
			j++;
		}
		cac=false;
		cac1=false;
		if(!lis.size()&&!lis1.size()){
			wow[i][0]=true;
			wow[i][1]=true;
			continue;
		}
		if(lis.size()){
			ans1+=abs(coor[lis.back()].first-i)+abs(coor[lis.back()].second-1);
			used[lis.back()]=true;
			lis.pop_back();
			cac=true;
		}
		if(lis1.size()){
			ans1+=abs(coor[lis1.back()].first-i)+abs(coor[lis1.back()].second-2);
			used[lis1.back()]=true;
			lis1.pop_back();
			cac1=true;
		}
		if(cac&&cac1){
			continue;
		}
		if(!cac){
			if(lis1.size()){
				ans1+=abs(coor[lis1.back()].first-i)+abs(coor[lis1.back()].second-1);
				used[lis1.back()]=true;
				lis1.pop_back();
			}
			else{
				wow[i][0]=true;
			}
			continue;
		}
		if(lis.size()){
			ans1+=abs(coor[lis.back()].first-i)+abs(coor[lis.back()].second-2);
			used[lis.back()]=true;
			lis.pop_back();
		}
		else{
			wow[i][1]=true;
		}
	}
	//cout<<"ditmemay "<<ans1<<endl;
	lis.clear();
	lis1.clear();
	j=2*n;
	for(i=n;i>=1;i--){
		while(j&&coor[j].first>=i){
			if(!used[j]){
				if(coor[j].second>=2){
					lis1.push_back(j);
				}
				else{
					lis.push_back(j);
				}
			}
			j--;
		}
		if(!wow[i][0]&&!wow[i][1]){
			continue;
		}
		if(wow[i][0]){
			if(lis.size()){
				ans1+=abs(coor[lis.back()].first-i)+abs(coor[lis.back()].second-1);
				lis.pop_back();
				wow[i][0]=false;
			}
		}
		if(wow[i][1]){
			if(lis1.size()){
				ans1+=abs(coor[lis1.back()].first-i)+abs(coor[lis1.back()].second-2);
				lis1.pop_back();
				wow[i][1]=false;
			}
		}
		if(wow[i][0]){
			if(lis1.size()){
				ans1+=abs(coor[lis1.back()].first-i)+abs(coor[lis1.back()].second-1);
				lis1.pop_back();
				wow[i][0]=false;
			}
		}
		if(wow[i][1]){
			if(lis.size()){
				ans1+=abs(coor[lis.back()].first-i)+abs(coor[lis.back()].second-2);
				lis.pop_back();
				wow[i][1]=false;
			}
		}
	}
	cout<<min(ans,ans1);
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63