#include <bits/stdc++.h>
#define int long long
#define INF 100000000
using namespace std;
int n;
int fix(map<int, int> &mp, vector<int> &src, vector<int> &dest){
int cost = 0;
priority_queue<pair<int, int>> pq;
for(int i = 1;i<=n;i++) pq.push({mp[i], i});
int totake = (src.size() - n);
while(totake--){
pair<int, int> curr = pq.top();
pq.pop();
dest.push_back(curr.second);
curr.first--;
pq.push(curr);
cost++;
}
src.clear();
while(!pq.empty()){
pair<int, int> curr = pq.top();
pq.pop();
while(curr.first--) src.push_back(curr.second);
}
sort(src.begin(), src.end());
sort(dest.begin(), dest.end());
return cost;
}
int calcans(vector<int> &a, vector<int> &b){
int cost = 0;
for(int i = n;i>=1;i--){
if(a.size() < b.size()) swap(a, b);
int costa = INF, costb = INF, costc = INF;
int bestcost = INF;
//both from a
if(a.size() >= 2){
costa = min(costa, abs(i - a[a.size()-1]) + abs(i - a[a.size()-2]) + 1);
bestcost = min(bestcost, costa);
}
//both from b
if(b.size() >= 2){
costb = min(costb, abs(i - b[b.size()-1]) + abs(i - b[b.size()-2]) + 1);
bestcost = min(bestcost, costb);
}
//one from each
if(a.size() && b.size()){
costc = min(costc, abs(i - a[a.size()-1]) + abs(i - b[b.size()-1]));
bestcost = min(bestcost, costc);
}
if(a.size()==b.size()){
if(costc==bestcost){
a.pop_back();
b.pop_back();
}
else if(costb==bestcost){
b.pop_back();
b.pop_back();
}
else{
a.pop_back();
a.pop_back();
}
}
else{
if(costa==bestcost){
a.pop_back();
a.pop_back();
}
else if(costc==bestcost){
b.pop_back();
a.pop_back();
}
else{
b.pop_back();
b.pop_back();
}
}
cost+=bestcost;
}
return cost;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
priority_queue<pair<int, int>> p;
int cost = 0;
vector<int> v[2];
map<int, int> mp[2];
for(int i = 0;i<(2*n);i++){
int x, y;
cin>>x>>y;
if(y<=1){
cost+=(1 - y);
y = 1;
}
else{
cost+=(y - 2);
y = 2;
}
if(x<1){
cost += (1 - x);
x = 1;
}
if(x>n){
cost += (x - n);
x = n;
}
//cout<<i<<" "<<x<<" "<<y<<" "<<cost<<endl;
v[y-1].push_back(x);
mp[y-1][x]++;
}
for(int i = 0;i<2;i++){
if(v[i].size() > n) cost += fix(mp[i], v[i], v[1 - i]);
}
cost+=calcans(v[0], v[1]);
cout<<cost<<endl;
}
/*
5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3
*/
Compilation message
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:114:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v[i].size() > n) cost += fix(mp[i], v[i], v[1 - i]);
~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
