Advertisement
Guest User

Untitled

a guest
Dec 5th, 2019
472
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> ii;
  5. typedef pair<char, int> ci;
  6.  
  7. mt19937 rng(time(0));
  8.  
  9. vector<string> a;
  10.  
  11. struct cmp{
  12.     long long operator()(const ii aa) const{
  13.         return (1LL*aa.first<<32) + aa.second;
  14.     }
  15.     long long operator()(const ci aa) const{
  16.         return (1LL*aa.second<<32) + aa.first;
  17.     }
  18. };
  19.  
  20. int nope(int ret){
  21.    return ret^((1<<5)-1);
  22. }
  23. unordered_set<ii, cmp> ans;
  24. vector<vector<int>> indices;
  25. unordered_map<ci, int, cmp> hashed;
  26. long long mx = 1e18;
  27.  
  28. void solve(){
  29.    ci par;
  30.    int idx = 0;
  31.    hashed.clear();
  32.    for(const auto & x : a){
  33.        int ret = 0;
  34.        if((int)ans.size() >= mx) return;
  35.        for(int j = 0; j < 5; j++){
  36.            par = {x[j], j};
  37.            if(hashed.count(par) == 0){
  38.                hashed[par] = rng()%2;
  39.            }
  40.            ret|=(hashed[par]<<j);
  41.        }
  42.        indices[ret].push_back(++idx);
  43.    }
  44.  
  45.    for(int i = 0 ; i < (1<<5); i++){
  46.        for(const auto &j : indices[i]){
  47.            for(int ret = indices[nope(i)].size()-1; ret >=0; ret--){
  48.                int jj = indices[nope(i)][ret];
  49.                if((int)ans.size() >= mx) return;
  50.                ans.insert({j < jj ? j : jj, j < jj ? jj : j});
  51.            }
  52.        }
  53.        indices[i].clear();
  54.        indices[nope(i)].clear();
  55.    }
  56. }
  57.  
  58. int main(){
  59.     cout.tie(NULL), cin.tie(NULL);
  60.     ios_base::sync_with_stdio(false);
  61.     int n;
  62.     cin >> n;
  63.     indices.resize(1<<5);
  64.     a.resize(n);
  65.     mx = min(100000*1LL, 1LL*n*(n+1)/2);
  66.     for(int i = 0; i < n; i++){
  67.         cin >> a[i];
  68.     }
  69.  
  70.     for(int i = 0; i < 600 && (int)ans.size() < mx; i++){
  71.         solve();
  72.     }
  73.  
  74.     auto it = ans.begin();
  75.     printf("%lld\n", min((long long)ans.size(), mx));
  76.     for(int i = 0; i < (int)ans.size() && i < mx; i++){
  77.         printf("%d %d\n", it->second, it->first);
  78.         ++it;
  79.     }
  80.  
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement