fork download
copy 
  1. /*
  2. ==> Don't stop when you're tired, stop when you're done.
  3. ==> Don't forget from the river to the sea palestine will be free 
  4. --> @author: MIDORIYA_
  5. */
  6. //*==============================================================
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. typedef long long ll;
  10. typedef double db;
  11. typedef long double ld;
  12. typedef pair<int, int> pii;
  13. typedef pair<ll, ll> pll;
  14. typedef vector<int> vi;
  15. typedef vector<ll> vll;
  16. typedef vector<db> vd;
  17. typedef vector<ld> vld;
  18. typedef vector<bool> vb;
  19. typedef vector<vector<ll>> vvl;
  20. typedef vector<vector<int>> vvi;
  21. typedef vector<pii> vii;
  22. typedef set<int> si;
  23. typedef set<ll> sl;
  24. #define pb push_back
  25. #define all(x) x.begin(), x.end()
  26. #define rall(x) x.rbegin(), x.rend()
  27. #define endl "\n"
  28. const ll MOD = 998244353, mod = 1e9 + 7, maxA = 1e5 + 5;
  29. #define time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << endl;
  30. //*===================>>>Fast-IO-Functions<<<=================
  31. void fastIO()
  32. {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(nullptr);
  35.     cout.tie(nullptr);
  36. }
  37. //*===================>>>File-IO-Functions<<<=================
  38. void fileIO()
  39. {
  40. #ifndef ONLINE_JUDGE
  41.     freopen("in.txt", "r", stdin);
  42.     freopen("out.txt", "w", stdout);
  43. #endif
  44. }
  45. //*===================>>>ONE-FOR-ALL-Function<<<==============
  46. void OneForAll()
  47. {
  48.     ll n;
  49.     cin >> n;
  50.     vector <pii> cards(n);
  51.     map<int, int> front, back, both;
  52.  
  53.     for (int i = 0; i < n; i++)
  54.     {
  55.         int a, b;
  56.         cin >> a >> b;
  57.         cards[i] = {a, b};
  58.  
  59.         front[a]++;
  60.         if(a != b)
  61.         {
  62.             back[b]++;
  63.         }
  64.         if(a == b)
  65.         {
  66.             both[a]++;
  67.         }
  68.     }
  69.  
  70.     ll need = (n + 1) / 2;
  71.     ll ans = LLONG_MAX;
  72.  
  73.     set<int> colors; 
  74.     for(auto &c : cards)
  75.     {
  76.         colors.insert(c.first); // front;
  77.         colors.insert(c.second); // back;
  78.     }
  79.  
  80.     for(int color : colors)
  81.     {
  82.         ll cntFront = front[color], cntBack = back[color];
  83.  
  84.         // color is present only in front
  85.         // can't satisfy the conditions
  86.         if(cntFront >= need)
  87.         {
  88.             ans = 0;
  89.             break;
  90.         }
  91.  
  92.         ll rem = need - cntFront; // back
  93.  
  94.         if(cntBack >= rem)
  95.         {
  96.             ans = min(ans, rem);
  97.         }
  98.     }
  99.  
  100.     cout << (ans == LLONG_MAX ? -1 : ans) << endl;
  101. }
  102.  
  103. int main()
  104. {
  105.     fastIO();
  106.     fileIO();
  107.  
  108.     ll tc = 1;
  109.     // cin >> tc;
  110.     while(tc--)
  111.     {
  112.         // cout << "Case " << i << ": ";
  113.         OneForAll();
  114.     }
  115.     time;
  116.     return 0;
  117. }
Success #stdin #stdout #stderr 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
stderr
copy 
Time Taken: 0.004398 Secs
https://ideone.com/WW5ask
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!