#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
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;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
