Submission #527580

#TimeUsernameProblemLanguageResultExecution timeMemory
527580vivaan_guptaMutating DNA (IOI21_dna)C++17
35 / 100
36 ms4996 KiB
#include "dna.h" // #include <iostream> using namespace std; const int N = 1e5 + 5; int pre[N]; int n; int ones[N], ones2[N]; void init(std::string a, std::string b) { n = a.size(); for(int i = 0;i < n;i++){ int cnt = (a[i] != b[i]); pre[i] = cnt; ones[i] = (a[i] =='A'); ones2[i] = (b[i] == 'A'); if(i > 0) { pre[i] += pre[i-1]; ones[i] += ones[i-1]; ones2[i] += ones2[i-1]; } } } int get_distance(int x, int y) { int A = ones[y], B = ones2[y]; if(x > 0) A -= ones[x - 1], B -= ones2[x - 1]; if(A != B){ return -1; } int sum = pre[y]; if(x > 0) sum -= pre[x - 1]; return (sum / 2); }
#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...