fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll            long long
  3. #define pb            emplace_back
  4. #define fi            first
  5. #define se            second
  6. #define mp            make_pair
  7. //#define int           int64_t
  8.  
  9. using namespace std;
  10.  
  11. typedef pair<ll, ll> pii;
  12. const int N = 4111;
  13.  
  14. ll p[N], k, sum[N][5], cur = 0, ss, ssum[N];
  15. int n, m;
  16. string s[N];
  17. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  18.  
  19. int Code(char c) {
  20.     if(c == 'A') return 1;
  21.     if(c == 'C') return 2;
  22.     if(c == 'T') return 3;
  23.     return 0;
  24. }
  25.  
  26. int main() {
  27.     ios_base::sync_with_stdio(0);
  28.     cin.tie(0); cout.tie(0);
  29.     #define FileName      "test"
  30.     if(fopen(FileName".inp", "r")) {
  31.        freopen(FileName".inp", "r", stdin);
  32.        freopen(FileName".out", "w", stdout);
  33.     }
  34.     cin >> n >> m >> k;
  35.     for(int i = 1; i <= n; ++i) {
  36.         p[i] = uniform_int_distribution<ll>((ll)1e9, (ll)1e11)(rng);
  37.         cin >> s[i];
  38.         for(int j = 0; j < m; ++j) sum[j][Code(s[i][j])] += p[i];
  39.         cur += p[i] * k;
  40.     }
  41.     for(int i = 0; i < m; ++i) {
  42.         ssum[i] = 0;
  43.         for(int j = 0; j < 4; ++j) ssum[i] += sum[i][j];
  44.     }
  45.     for(int i = 1; i <= n; ++i) {
  46.         ss = 0;
  47.         for(int j = 0; j < m; ++j) ss += (ssum[j] - sum[j][Code(s[i][j])]);
  48.         if(cur - p[i] * k == ss) return cout << i, 0;
  49.     }
  50. }
  51.  
Success #stdin #stdout 0s 4436KB
comments (?)
stdin
copy 
4 4 3
CATT
CAAA
ATGA
TCTA
stdout
copy 
4
https://ideone.com/t4PBfD
language:
C++14 (gcc 8.3)
created:
4 years 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!