Submission #437403

#	Time	Username	Problem	Language	Result	Execution time	Memory
437403		SAAD	Mutating DNA (IOI21_dna)	C++17	0 / 100	56 ms	8060 KiB

dna

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue> 
#include <string.h>
//#include "wall.h"
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
string dna = "ATC";
int aa[3][100002], bb[3][100002] , seg[100002][3][3] , ans[3][3] ;
int toidx( char x ) {
    if (x == 'A') return 0;
    if (x == 'T') return 1;
    return 2;
}
void init(string a, string b) {
    for (int i = 0; i < a.length(); i++) {
        seg[i][toidx(a[i])][toidx(b[i])]++;
        if (i) {
            for (auto j : dna) {
                for (auto u : dna) {
                    seg[i][toidx(j)][toidx(u)] += seg[i - 1][toidx(j)][toidx(u)];
                }
            }
        }

        aa[toidx(a[i])][i]++;
        bb[toidx(b[i])][i]++;
        if (i) {
            for (auto j:dna) {
                aa[toidx(j)][i] += aa[toidx(j)][i - 1];
                bb[toidx(j)][i] += bb[toidx(j)][i - 1];
            }
        }
    }
}
int get_distance(int x, int y) {
    for (auto j : dna) {
        int A = aa[toidx(j)][y] - (x>0?aa[toidx(j)][x-1]:0);
        int B = bb[toidx(j)][y] - (x>0?bb[toidx(j)][x-1]:0);
        if (A != B) return -1;
    }
    for (auto i : dna) {
        for (auto j : dna) {
            ans[toidx(i)][toidx(j)] = seg[y][toidx(i)][toidx(j)] - (x > 0 ? seg[x - 1][toidx(i)][toidx(j)]:0);
        }
    }
    int res = 0 , res1 = 0 ;
    for (int i = 0; i < 3; i++) {
        for (int j = i+1; j < 3; j++) {
            res += max(ans[i][j],ans[j][i]) - min(ans[i][j], ans[j][i]);
            res1 = min(ans[i][j], ans[j][i]);
        }
    }
    return ((res / 3) * 2) + res1;
}

Compilation message (stderr)

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

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