Submission #496985

#	Time	Username	Problem	Language	Result	Execution time	Memory
496985		Ierus	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	0 ms	204 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define int long long
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e6+777;
const int MOD = 1e9+7;
int n;
pair<int,int> edge[N];
int dist(int x1, int y1, int x2, int y2){
	return (abs(x1 - x2) + abs(y1 - y2));
}
set<tuple<int,int,int>> st;
map<pair<int,int>,bool>used;
bool pp[N];
int cnt1, cnt2;
signed main(){
	int n1; cin >> n1;
	for(int i = 1; i <= 2 * n1; ++i){
		int x, y;
		cin >> x >> y;  
//		if(1 <= x && x <= n1 && 1 <= y && y <= 2 && !used.count({x,y})){
//			if(y == 1) ++cnt1;
//			else ++cnt2;
//			used[{x,y}] = true;
//		}else{
			edge[++n] = {x, y};
//		}
	}sort(edge+1,edge+1+n);
	vector<pair<int,int>> v;
	for(int i = 1; i <= n; ++i){
		v.pb({edge[i].S, i});
	}sort(all(v));
	vector<tuple<int,int,int>> f, s;
	int res1 = 0, res2 = 0, pos1 = 0, pos2 = 0;
	for(int i = 0; i < sz(v); ++i){
		if(used.count({edge[v[i].S].F, edge[v[i].S].S}))continue;
		if(1 <= edge[v[i].S].F && edge[v[i].S].F <= n1 && 1 <=  edge[v[i].S].S &&  edge[v[i].S].S <= 2){
			if(edge[v[i].S].S == 1){
				s.pb({v[i].S,edge[v[i].S].F, edge[v[i].S].S});
				++cnt2;
			}else{
				++cnt1;
				f.pb({v[i].S,edge[v[i].S].F, edge[v[i].S].S});
			}
			pp[i] = true;
			used[{edge[v[i].S].F, edge[v[i].S].S}] = true;
		}
	}
	for(int i = 0; i < sz(v); ++i){
		if(pp[i])continue;
		if(cnt1 < n1){
			++cnt1;
			f.pb({v[i].S,edge[v[i].S].F, edge[v[i].S].S});
		}else{
			s.pb({v[i].S,edge[v[i].S].F, edge[v[i].S].S});
		}
	}
	sort(all(f)),sort(all(s));
	int res = 0;
	for(auto[p,x1, y1] : f){
//		while(used.count({++pos1, 1}));
		res += dist(x1, y1, ++pos1, 1);
//				cerr << "p: " << p << " {" << x1 << ", " << y1 << "} - " << "{" << pos1 << ", " << 1 << "}\n";

	}
	for(auto[p,x1, y1] : s){
//		while(used.count({++pos2, 2}));
		res += dist(x1, y1, ++pos2, 2);
//				cerr << "p: " << p << " {" << x1 << ", " << y1 << "} - " << "{" << pos2 << ", " << 2 << "}\n";

	}
	cout << res;
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:47:6: warning: unused variable 'res1' [-Wunused-variable]
   47 |  int res1 = 0, res2 = 0, pos1 = 0, pos2 = 0;
      |      ^~~~
joi2019_ho_t4.cpp:47:16: warning: unused variable 'res2' [-Wunused-variable]
   47 |  int res1 = 0, res2 = 0, pos1 = 0, pos2 = 0;
      |                ^~~~

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