제출 #532649

#제출 시각아이디문제언어결과실행 시간메모리
532649sidonGenetics (BOI18_genetics)C++17
46 / 100
2004 ms104600 KiB
#pragma GCC optimize("O3", "unroll-loops") #pragma GCC target("avx", "avx2", "popcnt") #include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int Z = 4100; struct Bitset { using num = unsigned long long; static const int B = 1<<6; #define setBit(X, I) (X ^= (num(-1) ^ X) & (num(1)<<(I))) #define blk(X) ((X)>>6) num v[blk(Z<<2)+1] {}; void assign(const int &i) { setBit(v[blk(i)], (i & 63)); } inline int countAnd(const Bitset &x) const { int res = 0; for(int i = blk(Z<<2); i >= 0; --i) res += __builtin_popcountll(v[i] & x.v[i]); return res; } void flip() { for(num &i : v) i = ~i; } }; int N, M, K; Bitset a[Z]; int g[100]; bool chk[Z][Z]; int cnt[Z][Z]; int main() { ios::sync_with_stdio(0), cin.tie(0); g['C'] = 1; g['G'] = 2; g['T'] = 3; cin >> N >> M >> K; int o[N]; for(int i = 0; i < N; ++i) { string inp; cin >> inp; for(int j = 0; j < M; ++j) a[i].assign(g[int(inp[j])] * Z + j); o[i] = i; } shuffle(o, o + N, rng); for(const int &i : o) { bool ok = 1; a[i].flip(); for(int j = 0; j < N; ++j) if(i != j) { int c = (chk[i][j] ? cnt[i][j] : a[i].countAnd(a[j])); chk[j][i] = 1; cnt[j][i] = c; if(c != K) { ok = 0; break; } } if(ok) { cout << i + 1; return 0; } a[i].flip(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...