Submission #1189602

#TimeUsernameProblemLanguageResultExecution timeMemory
1189602Panda50OMutating DNA (IOI21_dna)C++20
100 / 100
25 ms8456 KiB
// #include<iostream> #include "dna.h" using namespace std; const int mxN = 1e5+5; int qs_a[mxN][3]; int qs_b[mxN][3]; int pp[mxN][3][3]; bool can(int x, int y) { if((qs_a[y][0] - qs_a[x-1][0]) != (qs_b[y][0] - qs_b[x-1][0])) return false; if((qs_a[y][1] - qs_a[x-1][1]) != (qs_b[y][1] - qs_b[x-1][1])) return false; if((qs_a[y][2] - qs_a[x-1][2]) != (qs_b[y][2] - qs_b[x-1][2])) return false; return true; } int parse(char c) { if(c == 'A') return 0; if(c == 'C') return 1; return 2; } void reset(int i) { for(int j = 0; j < 3; ++j) { qs_a[i][j] = qs_a[i-1][j]; qs_b[i][j] = qs_b[i-1][j]; } for(int j = 0; j < 3; ++j) { for(int k = 0; k < 3; ++k) { pp[i][j][k] = pp[i-1][j][k]; } } return; } void init(string a, string b) { int n = a.size(); for(int i = 1; i <= n; ++i) { reset(i); if(parse(a[i-1]) == parse(b[i-1])) continue; qs_a[i][parse(a[i-1])] = qs_a[i-1][parse(a[i-1])] + 1; qs_b[i][parse(b[i-1])] = qs_b[i-1][parse(b[i-1])] + 1; pp[i][parse(a[i-1])][parse(b[i-1])] = pp[i-1][parse(a[i-1])][parse(b[i-1])] + 1; // cout << pp[i][parse(a[i-1])][parse(b[i-1])] << ' ' << parse(a[i-1]) << ' ' << parse(b[i-1]) << '\n'; } } int get_distance(int x, int y) { ++x, ++y; if(!can(x,y)) { return -1; } int cnt = 0; for(int i = 0; i < 3; ++i) { cnt += qs_a[y][i] - qs_a[x-1][i]; } int cnt_pair = 0; for(int i = 0; i < 3; ++i) { for(int j = i+1; j < 3; ++j) { int p1 = pp[y][i][j] - pp[x-1][i][j]; int p2 = pp[y][j][i] - pp[x-1][j][i]; if(p1 > 0 && p2 > 0){ // มีคู่ตรงข้ามกัน cnt_pair += min(p1, p2); cnt -= min(p1, p2) * 2; } } } // cout << pp[0][1]; // return cnt_pair; return cnt_pair + (cnt/3)*2; // return (all - cnt_pair) % 3 * 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...