Submission #439336

#	Time	Username	Problem	Language	Result	Execution time	Memory
439336		fvogel499	Mutating DNA (IOI21_dna)	C++17	71 / 100	1577 ms	8704 KiB

dna

#include <bits/stdc++.h>
 
using namespace std;
 
const int siz = 100010;
 
int psA [3][siz];
int psB [3][siz];
int insteadOf [3][3][siz];
 
int conv(char c) {
    if (c == 'A') return 0;
    else if (c == 'T') return 1;
    else return 2;
}
 
void init(string a, string b) {
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < 3; j++) {
            psA[j][i] = 0;
            psB[j][i] = 0;
            for (int k = 0; k < 3; k++) {
                insteadOf[j][k][i] = 0;
            }
        }
    }
    for (int i = 0; i < a.size(); i++) {
        psA[conv(a[i])][i]++;
        psB[conv(b[i])][i]++;
        insteadOf[conv(a[i])][conv(b[i])][i]++;
    }
    for (int i = 1; i < a.size(); i++) {
        for (int j = 0; j < 3; j++) {
            psA[j][i] += psA[j][i-1];
            psB[j][i] += psB[j][i-1];
            for (int k = 0; k < 3; k++) {
                insteadOf[j][k][i] += insteadOf[j][k][i-1];
            }
        }
    }
}
 
int get_distance(int x, int y) {
    for (int i = 0; i < 3; i++) {
        int aSum = psA[i][y];
        int bSum = psB[i][y];
        if (x > 0) {
            aSum -= psA[i][x-1];
            bSum -= psB[i][x-1];
        }
        if (aSum != bSum) {
            return -1;
        }
    }
    int ins [3][3];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            ins[i][j] = insteadOf[i][j][y];
            if (x > 0) ins[i][j] -= insteadOf[i][j][x-1];
        }
    }
    for (int i = 0; i < 3; i++) ins[i][i] = 0;
    int count = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            while (ins[i][j] and ins[j][i]) {
                count++;
                ins[i][j]--;
                ins[j][i]--;
            }
        }
    }
    int cycleLeft = 0;
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) cycleLeft = max(cycleLeft, ins[i][j]);
    count += 2*cycleLeft;
    return count;
}
 
// int main() {
//     string a, b;
//     cin >> a >> b;
//     init(a, b);
//     int q;
//     cin >> q;
//     for (int i = 0; i < q; i++) {
//         int x, y;
//         cin >> x >> y;
//         cout << get_distance(x, y) << endl;
//     }
//     int d = 0;
//     d++;
// }

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
dna.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
dna.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 1; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~

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