Submission #1142371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142371		FZ_Laabidi	Mutating DNA (IOI21_dna)	C++20	56 / 100	34 ms	4932 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;

int n, q; 
string a, b;
vector<int> pref;
vector<vector<int>> preff(2, vector<int>(n + 1)), pref2(2, vector<int>(n + 1));
// A is 0, T is 1
void init(string A, string B) {
    a = A;
    b = B;
    n = a.size();
    pref.resize(n + 1);
    preff[0].resize(n + 1);
    preff[1].resize(n + 1);
    pref2[0].resize(n + 1);
    pref2[1].resize(n + 1);

    preff[0][0]=0;
    pref2[0][1]=0;
    preff[0][0]=0;
    pref2[0][1]=0;
    pref[0]=0;
    int diff = 0, freqa1 = 0, freqa2 = 0, freqt1 = 0, freqt2 = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i-1] == 'T') freqt1++;
        if (a[i-1] == 'A') freqa1++;
        if (b[i-1] == 'A') freqa2++;
        if (b[i-1] == 'T') freqt2++;

        diff += (a[i-1] != b[i-1]);
        pref[i] = diff;
        preff[0][i] = freqa1;
        preff[1][i] = freqt1;
        pref2[0][i] = freqa2;
        pref2[1][i] = freqt2;
    }

    //for (int i = 0; i <= n; i++) cout << pref[i] << " ";
    //cout << endl;
}

int get_distance(int x, int y) {
    int dist = y - x + 1;
    if (y <= x + 2) {
        string s1 = "", s2 = "";
        map<int, int> freq1, freq2;
        for (int i = x; i <= y; i++) {
            s1.push_back(a[i]);
            s2.push_back(b[i]);
            freq1[a[i]]++;
            freq2[b[i]]++;
        }
        string o = "ATC";
        for (char c : o) {
            if (freq1[c] != freq2[c]) return -1;
        }

        int diff = 0;
        for (int i = 0; i < dist; i++) {
            if (s1[i] != s2[i]) diff++;
        }
        if (diff == 2) return 1;
        if (diff == 0) return 0;
        if (diff == 1) return -1;
        if (diff == 3) return 2;
    }
    int diff = pref[y + 1] - pref[x];
    int freqa1 = preff[0][y + 1] - preff[0][x];
    int freqa2 = pref2[0][y + 1] - pref2[0][x];
    int freqt1 = preff[1][y + 1] - preff[1][x];
    int freqt2 = pref2[1][y + 1] - pref2[1][x];
    //for(int i=0; i<pref2[1].size(); i++)cout << pref2[1][i]<< " ";
    //cout << endl;
    //cout << freqt1 <<" "<< freqt2 <<" " <<freqa1<< " " << freqa2 << endl;
    if ( freqt1 != freqt2 || freqa1 != freqa2) return -1;
    return diff / 2;
    

    return 0; 
}

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