Submission #117872

#TimeUsernameProblemLanguageResultExecution timeMemory
117872JohnTitorCoin Collecting (JOI19_ho_t4)C++11
100 / 100
43 ms6620 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll #define __builtin_popcount __builtin_popcountll using ll=long long; using ld=long double; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2; template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);} template <typename T> inline void writeln(T x){write(x); putchar('\n');} #define taskname "Coin" int n; int x[200001]; int y[200001]; int c[100001][3]; int main(){ #ifdef Aria if(fopen(taskname".in", "r")) freopen(taskname".in", "r", stdin); #endif // Aria read(n); FOR(i, 1, n*2) read(x[i]), read(y[i]); ll ans=0; FOR(i, 1, n*2){ if(x[i]<1){ ans+=1-x[i]; x[i]=1; } else if(x[i]>n){ ans+=x[i]-n; x[i]=n; } if(y[i]<1){ ans+=1-y[i]; y[i]=1; } else if(y[i]>2){ ans+=y[i]-2; y[i]=2; } } FOR(i, 1, n*2) c[x[i]][y[i]]++; int d[3]={0, 0, 0}; FOR(i, 1, n){ d[1]+=c[i][1]-1; d[2]+=c[i][2]-1; if(d[1]>0&&0>d[2]){ int t=min(d[1], -d[2]); d[1]-=t; d[2]+=t; ans+=t; } if(0>d[1]&&d[2]>0){ int t=min(-d[1], d[2]); d[1]+=t; d[2]-=t; ans+=t; } ans+=abs(d[1]); ans+=abs(d[2]); } writeln(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...