Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int, int> ii;
- typedef pair<char, int> ci;
- mt19937 rng(time(0));
- vector<string> a;
- struct cmp{
- long long operator()(const ii aa) const{
- return (1LL*aa.first<<32) + aa.second;
- }
- long long operator()(const ci aa) const{
- return (1LL*aa.second<<32) + aa.first;
- }
- };
- int nope(int ret){
- return ret^((1<<5)-1);
- }
- unordered_set<ii, cmp> ans;
- vector<vector<int>> indices;
- unordered_map<ci, int, cmp> hashed;
- long long mx = 1e18;
- void solve(){
- ci par;
- int idx = 0;
- hashed.clear();
- for(const auto & x : a){
- int ret = 0;
- if((int)ans.size() >= mx) return;
- for(int j = 0; j < 5; j++){
- par = {x[j], j};
- if(hashed.count(par) == 0){
- hashed[par] = rng()%2;
- }
- ret|=(hashed[par]<<j);
- }
- indices[ret].push_back(++idx);
- }
- for(int i = 0 ; i < (1<<5); i++){
- for(const auto &j : indices[i]){
- for(int ret = indices[nope(i)].size()-1; ret >=0; ret--){
- int jj = indices[nope(i)][ret];
- if((int)ans.size() >= mx) return;
- ans.insert({j < jj ? j : jj, j < jj ? jj : j});
- }
- }
- indices[i].clear();
- indices[nope(i)].clear();
- }
- }
- int main(){
- cout.tie(NULL), cin.tie(NULL);
- ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- indices.resize(1<<5);
- a.resize(n);
- mx = min(100000*1LL, 1LL*n*(n+1)/2);
- for(int i = 0; i < n; i++){
- cin >> a[i];
- }
- for(int i = 0; i < 600 && (int)ans.size() < mx; i++){
- solve();
- }
- auto it = ans.begin();
- printf("%lld\n", min((long long)ans.size(), mx));
- for(int i = 0; i < (int)ans.size() && i < mx; i++){
- printf("%d %d\n", it->second, it->first);
- ++it;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement