Submission #877813

#TimeUsernameProblemLanguageResultExecution timeMemory
877813phoenix0423Genetics (BOI18_genetics)C++17
100 / 100
453 ms36528 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define fastio ios::sync_with_stdio(false), cin.tie(0) // #pragma GCC optimize("Ofast") #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define REP1(i, n) FOR(i, 0, n + 1) #define pb push_back #define pf push_front #define eb emplace_back #define f first #define s second #define lowbit(x) x&-x #define ckmin(a, b) a = min(a, b) #define ckmax(a, b) a = max(a, b) const int N = 1e9 + 7; const int INF = 1e9 + 7; const int maxn = 5000; ll have[maxn][4]; map<char, int> mp{{'A', 0}, {'T', 1}, {'C', 2}, {'G', 3}}; int main(void){ fastio; int n, m, k; cin>>n>>m>>k; vector<string> s(n); for(int i = 0; i < n; i++) cin>>s[i]; random_device rd; mt19937 gen; uniform_int_distribution<> rng(0, INF); vector<int> w(n); ll ttlw = 0; for(int i = 0; i < n; i++) w[i] = rng(gen), ttlw += w[i]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++) have[j][mp[s[i][j]]] += w[i]; } for(int i = 0; i < n; i++){ ll dif = 0; for(int j = 0; j < m; j++){ dif += ttlw - have[j][mp[s[i][j]]]; } if(dif == (ttlw - w[i]) * k){ cout<<i + 1<<"\n"; return 0; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...