oj.uz

Submission #126550

# Submission time Handle Problem Language Result Execution time Memory
126550 2019-07-08T04:41:55 Z HungAnhGoldIBO2020 Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 2 ms 376 KB 
#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;
	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;
			}
		}
	}
	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;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -