SHARE
TWEET

Untitled

a guest May 22nd, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. #define pii pair<long long,long long>
  6. #define pll pair<long long, long long>
  7. #define rep(i,l,r) for(long long i = l;i<r;i++)
  8.  
  9. #define SSTR( x ) static_cast< std::ostringstream & >( \
  10.         ( std::ostringstream() << std::dec << x ) ).str()
  11.  
  12. #define fastout  ios_base::sync_with_stdio(false);cin.tie(NULL);
  13. using namespace std;
  14. using namespace __gnu_pbds;
  15.  
  16. typedef tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
  17.  
  18. const long long INF = (long long)1e9 + 7;
  19. const long long LLINF = (long long)1e18 + 7;
  20.  
  21. mt19937 mt('O' + '4' + 'K' + 'O');
  22.  
  23. void kekek()
  24. {
  25.    
  26.     mt();
  27.     #ifdef EB_UG
  28.         freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
  29.     #endif
  30.     #ifndef EB_UG
  31.         ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  32.     #endif
  33. }
  34.  
  35. struct match {
  36.     string s1;
  37.     int ind1;
  38.     string s2;
  39.     int ind2;
  40. };
  41.  
  42. map<string, int> indx;
  43. map<int, int> cnt;
  44.  
  45. int main() {
  46.     kekek();
  47.     int n;
  48.     cin >> n;
  49.     vector<match> turik(n);
  50.     set<string> heh;
  51.     for (int i = 0; i < n; i++) {
  52.         cin >> turik[i].s1;
  53.         cin >> turik[i].s2;
  54.         heh.insert(turik[i].s1);
  55.         heh.insert(turik[i].s2);
  56.     }
  57.     vector<string> peps;
  58.     for (auto it: heh) {
  59.         peps.push_back(it);
  60.     }
  61.     int pn = peps.size();
  62.     for (int i = 0; i < pn; i++) {
  63.         indx[peps[i]] = i;
  64.     }
  65.     for (auto &it: turik) {
  66.         it.ind1 = indx[it.s1];
  67.         it.ind2 = indx[it.s2];
  68.     }
  69.     for (auto it: turik) {
  70.         cnt[indx[it.s1]]++;
  71.         cnt[indx[it.s2]]++;
  72.     }
  73.     int need = (n + 1) >> 1;
  74.             vector<bool> used(n + 10);
  75.     vector<vector<int>> total(1000);
  76.  
  77.  
  78.     int ind = 0;
  79.     while(true) {
  80.         if (need == 1)
  81.             need *= 2;
  82.         int mn = INF;
  83.         for(auto it: cnt) {
  84.             if (it.second == 0)
  85.                 continue;
  86.             mn = min(mn, it.second);
  87.         }
  88.         if (mn == INF)
  89.             break;
  90.         vector<int> prek;
  91.         for (auto it: cnt) {
  92.             if (it.second == mn) {
  93.                 prek.push_back(it.first);
  94.             }
  95.         }
  96.         if (prek.size() != need) {
  97.             cout << "NO SOLUTION";
  98.             return 0;
  99.         }
  100.  
  101.         vector<int> del;
  102.         for (int i = 0; i < n; i++) {
  103.             if (used[i])
  104.                 continue;
  105.             if (cnt[turik[i].ind1] == 1 || cnt[turik[i].ind2] == 1) {
  106.                 used[i] = true;
  107.                 del.push_back(i);
  108.             }
  109.         }
  110.         for (auto it: del) {
  111.                 cnt[turik[it].ind1] = max(cnt[turik[it].ind1] - 1, 0);
  112.                 cnt[turik[it].ind2] = max(cnt[turik[it].ind2] - 1, 0);
  113.         }
  114.         total[ind] = prek;
  115.         ind++;
  116.         need >>= 1;
  117.     }
  118.     for (auto it: total[ind - 2]) {
  119.         cout << peps[it] << ' ';
  120.     }
  121. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top