제출 #896069

#제출 시각아이디문제언어결과실행 시간메모리
896069nifesheGenetics (BOI18_genetics)C++17
27 / 100
26 ms10588 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC target ("avx2") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #define f first #define s second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((int) (x).size()) #define pb push_back #define mp make_pair #define int long long using namespace std; using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; } template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; } typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const ll mod = 998244353; const ll base = 1e6 + 9; const ll inf = 1e18; const int MAX = 3e5 + 42; const int LG = 20; random_device rd; mt19937 gen(rd()); uniform_int_distribution<ll> dis(1, inf); void solve() { int n, m, k; cin >> n >> m >> k; vector<string> a(n); for(auto &i : a) { cin >> i; for(auto &j : i) j -= 'A'; } if(n * n * m <= 1e7) { for(int i = 0; i < n; i++) { bool ok = 1; for(int j = 0; j < n; j++) { if(j == i) continue; int cnt = 0; for(int p = 0; p < m && cnt <= k; p++) { cnt += a[i][p] != a[j][p]; } if(cnt != k) { ok = 0; break; } } if(ok) { cout << i + 1 << '\n'; return; } } assert(0); } const int BUBEN = 40; vector<vector<vector<int>>> have(BUBEN, vector<vector<int>>(m, vector<int>(4))); vector<int> cnt(BUBEN); vector<int> idx(n); for(int i = 0; i < n; i++) { idx[i] = dis(gen) % BUBEN; cnt[idx[i]]++; for(int j = 0; j < m; j++) { for(int c = 0; c < 4; c++) { have[idx[i]][j][c]++; } } } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { have[idx[i]][j][a[i][j]]--; } } vector<int> p(n); iota(all(p), 0); shuffle(all(p), gen); for(auto i : p) { int need = (cnt[idx[i]] - 1) * k; for(int j = 0; j < m && need >= 0; j++) { need -= have[idx[i]][j][a[i][j]]; } if(need == 0) { cout << i + 1 << '\n'; return; } } assert(0); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ttt = 1; // cin >> ttt; while(ttt--) { 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...