Advertisement
Guest User

Untitled

a guest
Aug 20th, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define forr(i, a, b) for(int i=(int)(a);i<(int)(b);i++)
  4. #define forn(i,n) forr(i,0,n)
  5. #define dforn(i,n) for(int i=(int)(n-1);i>=0;i--)
  6. #define forall(it, v) for(auto it=v.begin();it!=v.end();it++)
  7. #define pb push_back
  8. typedef long long ll;
  9. const int MAXN=100050;
  10.  
  11. int n;
  12. pair<int,int> W[MAXN];
  13. map<int,int> M;
  14.  
  15. int check(int t){
  16.     int g=0;
  17.     forn(i,n){
  18.         if(W[i].first==t)g++;
  19.     }
  20.     int ans=0;
  21.     forn(i,n){
  22.         if(W[i].first==t) continue;
  23.         if(g*2>=n) continue;
  24.         if(W[i].second==t){g++;ans++;}
  25.     }
  26.     return g*2>=n?ans:n+1;
  27. }
  28.  
  29. int main() {
  30.     //~ freopen("D.in", "r", stdin);
  31.     while(scanf("%d",&n)>=1){
  32.         M.clear();
  33.         forn(i,n){
  34.             int a,b;
  35.             scanf("%d%d",&a,&b);
  36.             W[i]=make_pair(a,b);
  37.             if(a==b){
  38.                 M[a]++;
  39.             } else {
  40.                 M[a]++;
  41.                 M[b]++;
  42.             }
  43.         }
  44.         vector<pair<int,int>> V;
  45.         for(auto it:M){
  46.             V.pb(make_pair(it.second,it.first));
  47.         }
  48.         sort(V.begin(),V.end());
  49.         reverse(V.begin(),V.end());
  50.         int t=min(10,(int)V.size());
  51.         int ans=n+1;
  52.         forn(i,t){
  53.             ans=min(ans,check(V[i].second));
  54.         }
  55.         printf("%d\n",ans==n+1?-1:ans);
  56.     }
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement