Submission #1236975

#TimeUsernameProblemLanguageResultExecution timeMemory
1236975i_love_mritiMutating DNA (IOI21_dna)C++20
0 / 100
23 ms10304 KiB
#include <bits/stdc++.h> #include "dna.h" using namespace std; const int mxN = 2e5 + 1000; string A, B; int dp[mxN][10]; void init(string a, string b){ A = a, B = b; memset(dp, 0, sizeof(dp)); for(int i = 1; i <= (int) a.size(); ++i){ for(int j = 0; j <= 9; ++j) dp[i][j] = dp[i - 1][j]; dp[i][0] += A[i] == 'A'; dp[i][0] -= B[i] == 'A'; dp[i][1] += A[i] == 'C'; dp[i][1] -= B[i] == 'C'; dp[i][2] += A[i] == 'T'; dp[i][2] -= B[i] == 'T'; dp[i][3] += A[i] == 'A' && B[i] == 'T'; dp[i][4] += A[i] == 'T' && B[i] == 'A'; dp[i][5] += A[i] == 'A' && B[i] == 'C'; dp[i][6] += A[i] == 'C' && B[i] == 'A'; dp[i][7] += A[i] == 'T' && B[i] == 'C'; dp[i][8] += A[i] == 'C' && B[i] == 'T'; dp[i][9] += A[i] == B[i]; } } int get(int x, int y, int t){ return dp[y][t] - dp[x - 1][t]; } int get_distance(int x, int y){ ++y, ++x; int a = get(x, y, 0), c = get(x, y, 1), t = get(x, y, 2), good = get(x, y, 9), at = get(x, y, 3), ta = get(x, y, 4), ac = get(x, y, 5), ca = get(x, y, 6), tc = get(x, y, 7), ct = get(x, y, 8); if(a == 0 && c == 0 && t == 0){ if(good == (y - x + 1)) return 0; int hehehe = ((y - x + 1) - min(at, ta) * 2 - min(ac, ca) * 2 - min(tc, ct) * 2 - good), one = 1, moves = 0; while(hehehe > 0){ if(one == 1) --hehehe; else hehehe -= 2; one = 1 - one; ++moves; } return min(at, ta) + min(ac, ca) + min(tc, ct) + moves; }else{ return -1; } } /*int main(){ #ifndef ONLINE_JUDGE freopen("inp.in", "r", stdin); freopen("output.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); init("ACTCAT", "TACACT"); cout << get_distance(0, 5) << endl; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...