Submission #441377

#	Time	Username	Problem	Language	Result	Execution time	Memory
441377		mariowong	Mutating DNA (IOI21_dna)	C++17	22 / 100	53 ms	7308 KiB

dna

#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++){
        if (i!= 0)
        ans[i]=ans[i-1];
        for (int j=0;j<3;j++){
            if (!q[j].empty() && 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 (x == 0){
            if (ct[y][i] != ct2[y][i])
            return -1;
        }
        else
        if (ct[y][i]-ct[x-1][i] != ct2[y][i]-ct2[x-1][i])
        return -1;
    }
    if (x == 0)
    return ans[y];
    return ans[y]-ans[x-1];
}
/*
string s,t;
int aa,bb;
int main(){
    cin >> s >> t;
    init(s,t);
    for (int i=1;i<=4;i++){
        cin >> aa >> bb;
        cout << get_distance(aa,bb) << "\n";
    }
}*/

• Subtask 1: 0 / 21
• Subtask 2: 22 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16