Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.19 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int r[2];
  5. long long ans;
  6. int c[100100][2];
  7. int main(){
  8. int n;
  9. cin>>n;
  10.  
  11. for(int i=0;i<n*2;i++){
  12. int x,y;
  13. cin>>x>>y;
  14. if(x<1){
  15. ans+=(1-x);
  16. x= 1;
  17.  
  18. }
  19. if(x>n){
  20. ans+=(x-n);
  21. x=n;
  22. }
  23. if(y<1){
  24. ans+=1-y;
  25. y=1;
  26. }
  27. if(y>2){
  28. ans+=y-2;
  29. y=2;
  30. }
  31. //shift all coins into the rectangle itself
  32. c[x][y-1]++;
  33. }
  34. for(int i=1;i<=n;i++){
  35. r[0]+=c[i][0]-1;
  36. r[1]+=c[i][1]-1;
  37. //go from l to r for the 2 columns, keeping track of the number of empty positions/ amount coins have had to move.
  38. for(int k=0;k<2;k++){
  39. if(r[k]>0 && r[!k]<0){
  40. //if coins can be shifted to empty positions in a different row, shift them
  41. int x = min(r[k],-1*r[!k]);
  42. ans+=x;
  43. r[k]-=x;
  44. r[!k]+=x;
  45. }
  46. }
  47. ans+=abs(r[0])+abs(r[1]);
  48. //amount coins have moved or will have to move
  49. }
  50. cout<<ans<<endl;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement