Submission #451954

#	Time	Username	Problem	Language	Result	Execution time	Memory
451954		iulia13	Mutating DNA (IOI21_dna)	C++17	100 / 100	57 ms	9716 KiB

dna

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const int L = 3;
int vA[N][L], vB[N][L];
int p[N][L][L];
map <char, int> mp;
void init(string a, string b)
{
    int n = a.size(), i, j, h;
    mp['A'] = 0;
    mp['C'] = 1;
    mp['T'] = 2;
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j < L; j++)
        {
            vA[i][j] = vA[i - 1][j];
            vB[i][j] = vB[i - 1][j];
        }
        for (j = 0; j < L; j++)
            for (h = 0; h < L; h++)
                p[i][j][h] = p[i - 1][j][h];
        int f = mp[a[i - 1]], s = mp[b[i - 1]];
        vA[i][f]++;
        vB[i][s]++;
        p[i][f][s]++;
    }
}
int get_distance(int x, int y)
{
    int i, j, h, cnt = 0, maxi = 0;
    y++;
    for (i = 0; i < L; i++)
        if (vA[y][i] - vA[x][i] != vB[y][i] - vB[x][i])
            return -1;
    for (i = 0; i < L; i++)
        for (j = i + 1; j < L; j++)
        {
            int a = p[y][i][j] - p[x][i][j];
            int b = p[y][j][i] - p[x][j][i];
            cnt += min(a, b);
            maxi = max(maxi, max(a, b) - min(a, b));
        }
    return cnt + 2 * maxi;

}/*
int main()
{

   int n, q;
	assert(scanf("%d %d", &n, &q) == 2);
	char A[n+1], B[n+1];
	assert(scanf("%s", A) == 1);
	assert(scanf("%s", B) == 1);
	std::string a = std::string(A);
	std::string b = std::string(B);
	std::vector<int> x(q), y(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);
	std::vector<int> results(q);
	init(a, b);
	for (int i = 0; i < q; i++) {
		results[i] = get_distance(x[i], y[i]);
	}
	for (int i = 0; i < q; i++) {
		printf("%d\n", results[i]);
	}
	fclose(stdout);
	return 0;
}*/

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:33:15: warning: unused variable 'h' [-Wunused-variable]
   33 |     int i, j, h, cnt = 0, maxi = 0;
      |               ^

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