제출 #441375

#제출 시각아이디문제언어결과실행 시간메모리
441375mariowongDNA 돌연변이 (IOI21_dna)C++17
0 / 100
37 ms12772 KiB
#include "dna.h" #include <bits/stdc++.h> using namespace std; int ct[100005][5],ct2[100005][5],n,ans[100005]; priority_queue <int> q[5]; char dd[5]={'A','C','T'}; void init(std::string a, std::string b) { n=a.length(); for (int i=0;i<n;i++){ for (int j=0;j<3;j++){ if (i!=0){ ct[i][j]=ct[i-1][j]; ct2[i][j]=ct2[i-1][j]; } if (a[i] == dd[j]){ ct[i][j]++; q[j].push(-i); } if (b[i] == dd[j]) ct2[i][j]++; } } for (int i=0;i<n;i++){ ans[i]=ans[i-1]; for (int j=0;j<3;j++){ if (q[j].top() == -i){ if (dd[j] == b[i]){ q[j].pop(); break; } for (int k=0;k<3;k++){ if (b[i] == dd[k]){ q[k].pop(); q[k].push(q[j].top()); q[j].pop(); ans[i]++; } } } } } } int get_distance(int x, int y) { for (int i=0;i<3;i++){ if (ct[y][i]-ct[x-1][i] != ct2[y][i]-ct2[x-1][i]) return -1; } return ans[y]-ans[x-1]; }
#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...