Submission #977838

#TimeUsernameProblemLanguageResultExecution timeMemory
977838efedmrlrGenetics (BOI18_genetics)C++17
0 / 100
110 ms10180 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("bmi,avx2,popcnt") #include <bits/stdc++.h> #define int long long int #define ld long double #define pb push_back #define MP make_pair #define all(x) x.begin(), x.end() #define rall(x) x.begin(), x.end() #define REP(i, n) for(int i = 0; (i) < (n); (i)++) using namespace std; void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const int N = 4102; const int INF = 1e9 + 500; const int MOD = 1000; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } array<array<bitset<N>, N>, 4> s; array<int, N> val; array<array<int, N>, 4> sum; vector<int> w(N, 0); int n, m, k; void solve() { cin >> n >> m >> k; int S = 0; REP(i, n) { w[i] = rng(); w[i] %= MOD; // cout << w[i] << " \n"; S += w[i]; S %= MOD; } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { char t; cin >> t; s[0][i][j] = (t == 'A'); s[1][i][j] = (t == 'C'); s[2][i][j] = (t == 'G'); s[3][i][j] = (t == 'T'); } } REP(z, 4) { REP(i, m) sum[z][i] = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(s[z][i][j]) { sum[z][j] += w[i]; sum[z][j] %= MOD; } } } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(!s[z][i][j]) continue; int x = sum[z][j] - w[i]; if(x < 0) x+= MOD; val[i] += x; val[i] %= MOD; } } // cout << "val:" << val[0] << "\n\n"; // REP(j, m) // cout << sum[z][j] << " amk\n"; } REP(i, n) { int sx = S - w[i]; if(sx < 0) sx+= MOD; int x = sx * (m - k); x %= MOD; if(x == val[i]) { cout << i + 1 << "\n"; } return; } } signed main() { fastio(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...