fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4.  
  5. const ll mod1 = 1000000007LL;
  6. const ll mod2 = 1000000009LL;
  7. const ll base = 257LL;
  8.  
  9. struct hashed_string{
  10.     public:
  11.     string s; ll n;
  12.     vector<pair<ll,ll>> prefix;
  13.     vector<pair<ll,ll>> pow;
  14.  
  15.     hashed_string(string a){
  16.         s = a; n = a.size();
  17.         prefix.assign(n, {0,0});
  18.         pow.assign(n+1, {0,0});
  19.         pow[0] = {1,1};
  20.  
  21.         for (int i = 1; i <= n; i++){
  22.             pow[i].first = (pow[i-1].first * base) % mod1;
  23.             pow[i].second = (pow[i-1].second * base) % mod2;
  24.         }
  25.  
  26.         ll sum1 = 0, sum2 = 0;
  27.  
  28.         for (int i = 0; i < n; i++){
  29.             ll c = s[i] - 'a' + 1;
  30.  
  31.             sum1 = (sum1 * base + c) % mod1;
  32.             sum2 = (sum2 * base + c) % mod2;
  33.  
  34.             prefix[i] = {sum1,sum2};
  35.         }
  36.     }
  37.  
  38.     hashed_string(){}
  39.  
  40.     pair<ll,ll> get_hash(ll l, ll r){
  41.         ll x1 = prefix[r].first;
  42.         ll x2 = prefix[r].second;
  43.  
  44.         if (l >= 1){
  45.             x1 = (x1 - prefix[l-1].first * pow[r-l+1].first % mod1 + mod1) % mod1;
  46.             x2 = (x2 - prefix[l-1].second * pow[r-l+1].second % mod2 + mod2) % mod2;
  47.         }
  48.  
  49.         return {x1,x2};
  50.     }
  51. };
  52.  
  53. void solve(){
  54.     ll n,k;
  55.     cin >> n >> k;
  56.  
  57.     vector<string> l1(n);
  58.     vector<hashed_string> v(n);
  59.  
  60.     for (int i = 0; i < n; i++) cin >> l1[i];
  61.  
  62.     if (k <= 2){
  63.         for (int i = 0; i < n; i++) cout << (n >= 2 ? '1' : '0');
  64.         cout << "\n";
  65.         return;
  66.     }
  67.  
  68.     for (int i = 0; i < n; i++) v[i] = hashed_string(l1[i]);
  69.  
  70.     string answ = "";
  71.     vector<bool> good(n,true);
  72.  
  73.     if (n > k){
  74.         vector<pair<pair<ll,ll>,ll>> dp[k][k];
  75.  
  76.         for (int i = 0; i < n; i++){
  77.             for (int j = 0; j < k; j++){
  78.                 for (int x = j+1; x < k; x++){
  79.  
  80.                     ll sum1 = 0;
  81.                     ll sum2 = 0;
  82.  
  83.                     if (j > 0){
  84.                         auto h = v[i].get_hash(0,j-1);
  85.                         sum1 = h.first;
  86.                         sum2 = h.second;
  87.                     }
  88.  
  89.                     if (x-j-1 >= 1){
  90.                         sum1 = sum1 * v[i].pow[x-j-1].first % mod1;
  91.                         sum2 = sum2 * v[i].pow[x-j-1].second % mod2;
  92.  
  93.                         auto h = v[i].get_hash(j+1,x-1);
  94.  
  95.                         sum1 = (sum1 + h.first) % mod1;
  96.                         sum2 = (sum2 + h.second) % mod2;
  97.                     }
  98.  
  99.                     if (k-x-1 >= 1){
  100.                         sum1 = sum1 * v[i].pow[k-x-1].first % mod1;
  101.                         sum2 = sum2 * v[i].pow[k-x-1].second % mod2;
  102.  
  103.                         auto h = v[i].get_hash(x+1,k-1);
  104.  
  105.                         sum1 = (sum1 + h.first) % mod1;
  106.                         sum2 = (sum2 + h.second) % mod2;
  107.                     }
  108.  
  109.                     dp[j][x].push_back({{sum1,sum2},i});
  110.                 }
  111.             }
  112.         }
  113.  
  114.         for (int i = 0; i < k; i++){
  115.             for (int j = i+1; j < k; j++){
  116.  
  117.                 sort(dp[i][j].begin(),dp[i][j].end());
  118.  
  119.                 for (int x = 0; x < n; x++){
  120.  
  121.                     if (x >= 1 &&
  122.                         dp[i][j][x-1].first == dp[i][j][x].first){
  123.                         good[dp[i][j][x].second] = false;
  124.                     }
  125.  
  126.                     if (x < n-1 &&
  127.                         dp[i][j][x].first == dp[i][j][x+1].first){
  128.                         good[dp[i][j][x].second] = false;
  129.                     }
  130.                 }
  131.             }
  132.         }
  133.     }
  134.     else{
  135.         for (int i = 0; i < n; i++){
  136.             for (int j = 0; j < n; j++){
  137.                 if (i != j){
  138.                     int cnt = 0;
  139.  
  140.                     for (int x = 0; x < k; x++){
  141.                         cnt += (l1[i][x] != l1[j][x]);
  142.                     }
  143.  
  144.                     if (cnt <= 2){
  145.                         good[i] = false;
  146.                     }
  147.                 }
  148.             }
  149.         }
  150.     }
  151.  
  152.     for (int i = 0; i < n; i++){
  153.         if (!good[i]) answ += '1';
  154.         else answ += '0';
  155.     }
  156.  
  157.     cout << answ << "\n";
  158. }
  159.  
  160. int main(){
  161.     ios::sync_with_stdio(false);
  162.     cin.tie(nullptr);
  163.  
  164.     int t;
  165.     cin >> t;
  166.  
  167.     while (t--)
  168.         solve();
  169.  
  170.     return 0;
  171. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SubDgs
language:
C++14 (clang 8.0)
created:
3 hours ago
visibility:
secret

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!