Submission #1154306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154306		Nahian9696	Mutating DNA (IOI21_dna)	C++17	0 / 100	26 ms	8604 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
string given, target;
vector<pair<long long, long long>> count_a (100001, {0, 0}), count_t (100001, {0, 0}), count_c (100001, {0, 0});
vector<long long> probs (100001, 0);

void init(string a, string b) {
    given = a;
    target = b;
    for (int i=0; i<a.size(); i++) {
        if (a[i]=='A')
        {
				count_a[i+1].first = count_a[i].first+1;
				count_t[i+1].first = count_t[i].first;
				count_c[i+1].first = count_c[i].first;
		}
		else if (a[i]=='T')
        {
				count_a[i+1].first = count_a[i].first;
				count_t[i+1].first = count_t[i].first+1;
				count_c[i+1].first = count_c[i].first;
		}
		else
        {
				count_a[i+1].first = count_a[i].first;
				count_t[i+1].first = count_t[i].first;
				count_c[i+1].first = count_c[i].first+1;
		}

		if (b[i]=='A')
        {
				count_a[i+1].second = count_a[i].second+1;
				count_t[i+1].second = count_t[i].second;
				count_c[i+1].second = count_c[i].second;
		}
		else if (b[i]=='T')
        {
				count_a[i+1].second = count_a[i].second;
				count_t[i+1].second = count_t[i].second+1;
				count_c[i+1].second = count_c[i].second;
		}
		else
        {
				count_a[i+1].second = count_a[i].second;
				count_t[i+1].second = count_t[i].second;
				count_c[i+1].second = count_c[i].second+1;
		}

		if (a[i]!=b[i])
			probs[i+1]=probs[i]+1;
		else
			probs[i+1]=probs[i];
    }
	cout << "probs = ";
	for (int i=1; i<=a.size(); i++) {
		cout << probs[i] << " ";
	}
	cout << "\n";
}

int get_distance(int x, int y) {
    if (((count_a[y+1].first-count_a[x].first)==(count_a[y+1].second-count_a[x].second))  &&
        ((count_t[y+1].first-count_t[x].first)==(count_t[y+1].second-count_t[x].second))  &&
        ((count_c[y+1].first-count_c[x].first)==(count_c[y+1].second-count_c[x].second))) {
        if (y-x<=2) {
            int prob=0;
            for (int i=x; i<=y; i++) {
                if (given[i]!=target[i])
                    prob++;
            }
            if (!prob)
                return 0;
            else
                return prob-1;
        }
		int ans = probs[y+1]-probs[x];
		return ans/2;
    }
    else {
        return -1;
    }

 return 0;
}

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