제출 #977771

#제출 시각아이디문제언어결과실행 시간메모리
977771efedmrlrGenetics (BOI18_genetics)C++17
46 / 100
2013 ms87684 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("bmi,avx2,popcnt") #include <bits/stdc++.h> #define lli 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 = 1e9 + 7; 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<array<int, N>, N> dif; int n, m, k; bitset<N> tmp; bitset<N> vis; void solve() { cin >> n >> m >> k; k *= 2; vector<int> perm(n), rperm(n); REP(i, n) perm[i] = i; REP(i, n) swap(perm[i], perm[rand(0, i)]); REP(i, n) rperm[perm[i]] = i; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { char t; cin >> t; s[0][perm[i]][j] = (t == 'A'); s[1][perm[i]][j] = (t == 'C'); s[2][perm[i]][j] = (t == 'G'); s[3][perm[i]][j] = (t == 'T'); } } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { REP(z, 4) { tmp = s[z][i] ^ s[z][j]; dif[i][j] += (int)tmp.count(); dif[j][i] += (int)tmp.count(); if(dif[i][j] > k) { break; } } if(dif[i][j] != k) { vis[i] = vis[j] = 1; } } if(!vis[i]) { cout << rperm[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...