# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
202575 | dndhk | Coin Collecting (JOI19_ho_t4) | C++14 | 92 ms | 6144 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAX_N = 100000;
int cnt[MAX_N+1][3];
int N;
ll ans = 0;
int main(){
scanf("%d", &N);
for(int i=1; i<=2*N; i++){
int x, y; scanf("%d%d", &x, &y);
if(x<=1 && y<=1){
cnt[1][1]++;
ans+=(ll)(1-x+1-y);
}else if(x<=1 && y>=2){
cnt[1][2]++;
ans+=(ll)(1-x+y-2);
}else if(x>=N && y<=1){
cnt[N][1]++;
ans+=(ll)(x-N+1-y);
}else if(x>=N && y>=2){
cnt[N][2]++;
ans+=(ll)(x-N+y-2);
}else if(y<=1){
cnt[x][1]++;
ans+=(ll)(1-y);
}else{
cnt[x][2]++;
ans+=(ll)(y-2);
}
}
for(int i=1; i<=N; i++){
for(int j=1; j<=2; j++) {
cnt[i][j]--;
}
}
int cnt2[3];
cnt2[1] = cnt2[2] = 0;
for(int i=1; i<=N; i++){
for(int j=1; j<=2; j++){
while(cnt[i][j]>0 && cnt2[j]<0){
cnt[i][j]--;
cnt2[j]++;
}
while(cnt[i][j]<0 && cnt2[j]>0){
cnt[i][j]++;
cnt2[j]--;
}
}
for(int j=1; j<=2; j++){
while(cnt[i][j]>0){
cnt[i][j]--;
if(cnt2[j]<0){
cnt2[j]++;
}else if(cnt2[3-j]<0){
cnt2[3-j]++;
ans+=1LL;
}else{
cnt2[j]++;
}
}
if(cnt[i][j]<0){
cnt[i][j]++;
if(cnt2[j]>0){
cnt2[j]--;
}else if(cnt2[3-j]>0){
cnt2[3-j]--;
ans+=1LL;
}else{
cnt2[j]--;
}
}
}
ans+=(ll)(cnt2[1]>0?cnt2[1]:-cnt2[1]);
ans+=(ll)(cnt2[2]>0?cnt2[2]:-cnt2[2]);
}
printf("%lld\n", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |