jakaria_hossain

codeforce - little elephant and cards

Jul 20th, 2019
131
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<pair<int,int> > v;
  4. int main()
  5. {
  6. int n,half;
  7. cin>>n;
  8. map<int,int>left,right;
  9. int x,y;
  10. if(n%2)
  11. half=n/2+1;
  12. else
  13. half=n/2;
  14.  
  15. //cout<<half<<endl;
  16. for(int i=0; i<n; i++)
  17. {
  18. cin>>x>>y;
  19. v.push_back(make_pair(x,y));
  20. left[x]++;
  21. right[y]++;
  22. if(x==y)right[y]--;
  23. }
  24. int ans=n;
  25. for(int i=0; i<n; i++)
  26. {
  27. if(left[v[i].first]>=half)
  28. {
  29. ans=0;
  30. break;
  31. }
  32. if(left[v[i].first]<half)
  33. {
  34. if(right[v[i].first]+left[v[i].first]>=half)
  35. {
  36. ans=min(ans,half-left[v[i].first]);
  37. }
  38. }
  39. if(right[v[i].first]+left[v[i].first]>=half)
  40. {
  41. ans=min(ans,half-left[v[i].first]);
  42. }
  43. if(right[v[i].second]+left[v[i].second]>=half)
  44. ans=min(ans,half-left[v[i].second]);
  45. if(right[v[i].second]>=half)
  46. ans=min(half,ans);
  47. }
  48. if(ans==n)
  49. ans=-1;
  50. cout<<ans<<endl;
  51. }
RAW Paste Data