Submission #232441

#	Time	Username	Problem	Language	Result	Execution time	Memory
232441		kshitij_sodani	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	84 ms	12908 KiB

joi2019_ho_t4

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo it[100001][2];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n;
	cin>>n;
	memset(it,0,sizeof(it));
	vector<pair<llo,llo>> ac;
	llo aa,bb;
	llo ans=0;
	llo freq[n][2];
	for(llo i=0;i<n;i++){
		freq[i][0]=0;
		freq[i][1]=0;
	}
	for(llo i=0;i<2*n;i++){
		cin>>aa>>bb;
		if(bb<=1){
			if(aa<1){
				it[0][0]+=1;
				ac.pb({0,0});
			}
			else if(aa>n){
				it[n-1][0]+=1;
				ac.pb({n-1,0});
			}
			else{
				it[aa-1][0]+=1;
				ac.pb({aa-1,0});
			}
		}
		else{
			if(aa<1){
				it[0][1]+=1;
				ac.pb({0,1});
			}
			else if(aa>n){
				it[n-1][1]+=1;
				ac.pb({n-1,1});
			}
			else{
				it[aa-1][1]+=1;
				ac.pb({aa-1,1});
			}
		}
		freq[ac.back().a][ac.back().b]+=1;
		ans+=abs(aa-(ac[i].a+1))+abs(bb-(ac[i].b+1));
	}
	queue<llo> cur[2];
	llo ind[2];
	ind[0]=0;
	ind[1]=0;
	/*for(auto j:ac){
		cout<<j.a<<","<<j.b<<endl;
	}*/
	for(llo i=0;i<n;i++){
		for(llo j=0;j<2;j++){
			for(llo k=0;k<freq[i][j];k++){
				cur[j].push(i);
			}
		}
		while(cur[0].size() and ind[0]<=i){
			ans+=abs(cur[0].front()-ind[0]);
			ind[0]+=1;
			cur[0].pop();
		}
		while(cur[1].size() and ind[1]<=i){
			ans+=abs(cur[1].front()-ind[1]);
			ind[1]+=1;
			cur[1].pop();
		}
		while(cur[0].size() and ind[1]<=i){
			ans+=abs(cur[0].front()-ind[1])+1;
			ind[1]+=1;
			cur[0].pop();
		}
		while(cur[1].size() and ind[0]<=i){
			ans+=abs(cur[1].front()-ind[0])+1;
			ind[0]+=1;
			cur[1].pop();
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

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