Submission #569503

#	Time	Username	Problem	Language	Result	Execution time	Memory
569503		PiejanVDC	Mutating DNA (IOI21_dna)	C++17	0 / 100	77 ms	18496 KiB

dna

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

vector<vector<int>>v;
vector<vector<int>>cntA,cntB;

int T(char a, char b) {
    if(a == 'A' && b == 'T')
        return 0;
    if(a == 'T' && b == 'A')
        return 1;
    if(a == 'C' && b == 'T')
        return 2;
    if(a == 'T' && b == 'C')
        return 3;
    if(a == 'C' && b == 'A')
        return 4;
    if(a == 'A' && b == 'C')
        return 5;
}

void init(string a, string b) {
    const int n = (int)a.length();
    v.resize(n+1, vector<int>(6,0));
    cntA.resize(n+1, vector<int>(3, 0));
    cntB.resize(n+1, vector<int>(3, 0));
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 0 ; j < 6 ; j++) {
            v[i][j] = v[i-1][j];
            if(T(a[i-1], b[i-1]) == j)
                v[i][j]++;
        }
    }
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 0 ; j < 3 ; j++) {
            cntA[i][j] = cntA[i-1][j];
            cntB[i][j] = cntB[i-1][j];
            if(j == 0 && a[i-1] == 'A')
                cntA[i][j]++;
            if(j == 1 && a[i-1] == 'T')
                cntA[i][j]++;
            if(j == 2 && a[i-1] == 'C')
                cntA[i][j]++;
            if(j == 0 && b[i-1] == 'A')
                cntB[i][j]++;
            if(j == 1 && b[i-1] == 'T')
                cntB[i][j]++;
            if(j == 2 && b[i-1] == 'C')
                cntB[i][j]++;
        }
    }
}

int get_distance(int x, int y) {
    x++,y++;
    vector<int>t(6);
    for(int i = 0 ; i < 6 ; i++)
        t[i] = v[y][i] - v[x-1][i];
    for(int i = 0 ; i < 3 ; i++) {
        if(cntA[y][i] - cntA[x-1][i] != cntB[y][i] - cntB[x-1][i])
            return -1;
    }
    int ans = 0;
    for(int i = 0 ; i < 6 ; i += 2) {
        int mn = min(t[i], t[i+1]);
        ans += mn;
        t[i] -= mn, t[i+1] -= mn;
    }
    int total = 0;
    for(auto z : t)
        total += z;
    if(total%3)
        return -1;
    ans += total/3 * 2;
    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int T(char, char)':
dna.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^

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