Submission #991659

#	Time	Username	Problem	Language	Result	Execution time	Memory
991659		wood	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	6936 KiB

dna

#include "dna.h"
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>
#include "dna.h"
#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay


using t = tuple<int,int,int>;
vi pa[3], pb[3];
vi res, res2;

void init(std::string a, std::string b) {
    char cc[3] = {'A', 'C', 'T'};
    int n = a.size();
    for(int i = 0; i<3; i++){
        pa[i].resize(n+1);
        pb[i].resize(n+1);
    }
    res.resize(n+1);
    res2.resize(n+1);
    for(int i = 0; i<n; i++){
        for(int j = 0; j<3; j++){
            pa[j][i+1] = pa[j][i] + (a[i] == cc[j]);
            pb[j][i+1] = pb[j][i] + (b[i] == cc[j]);
        }
        res[i+1] = res[i]+
        (a[i]=='A'&&b[i]!='A')+
        (a[i]=='T'&&b[i]=='C');
        res2[i+1] = res2[i]+
        (a[i]=='A'&&b[i]=='C')-
        (a[i]=='C'&&b[i]=='A');
    }
}

int get_distance(int x, int y) {
    for(int i = 0; i<3; i++){
        if(pa[i][y+1]-pa[i][x]!=pb[i][y+1]-pb[i][x]) return -1;
    }
    return res[y+1]-res[x]+max(res2[y+1]-res2[x],0);
}

// int main() {
//     #ifdef _WIN32
//         freopen("input.in", "r", stdin);
//         freopen("input.out", "w", stdout);
//     #endif
// 	int n, q;
// 	cin>>n>>q;
//     string a,b; cin>>a>>b;
// 	std::vector<int> x(q), y(q);
// 	for (int i = 0; i < q; i++) {
//         cin>>x[i]>>y[i];
// 	}
// 	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++) {
// 		cout<<results[i]<<'\n';
// 	}
// 	fclose(stdout);
// 	return 0;
// }

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