Submission #720842

#	Time	Username	Problem	Language	Result	Execution time	Memory
720842		urosk	Mutating DNA (IOI21_dna)	C++17	100 / 100	58 ms	19512 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define ll long long
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}

using namespace std;
#define maxn 100005
ll n;
ll ps[maxn][4][4];
ll p[maxn][4];
map<char,ll> mp;
void init(std::string a, std::string b) {
    mp['A'] = 1;
    mp['T'] = 2;
    mp['C'] = 3;
    n = a.size();
    for(ll i = 1;i<=n;i++){
       ll ca = mp[a[i-1]];
       ll cb = mp[b[i-1]];
       for(ll j = 1;j<=3;j++){
            p[i][j] = p[i-1][j];
            for(ll k = 1;k<=3;k++){
                ps[i][j][k] = ps[i-1][j][k];
            }
       }
       p[i][ca]++;
       p[i][cb]++;
       ps[i][ca][cb]++;
    }
}
ll f[4][4];
ll c[4];
ll cnt[4];
int get_distance(int x, int y) {
    x++; y++;
    for(ll i = 1;i<=3;i++) for(ll j = 1;j<=3;j++) f[i][j] = ps[y][i][j] - ps[x-1][i][j];
    for(ll i = 1;i<=3;i++) c[i] = 0;
    for(ll i = 1;i<=3;i++) cnt[i] = p[y][i] - p[x-1][i];
    ll ans = 0;
    set<ll> s;
    for(ll i = 1;i<=3;i++){
        for(ll j = i+1;j<=3;j++){
            ll x = min(f[i][j],f[j][i]);
            ans+=x;
            f[i][j]-=x;
            f[j][i]-=x;
            if(f[i][j]){
                c[i]++;
                s.insert(f[i][j]);
            }
            else if(f[j][i]){
                c[j]++;
                s.insert(f[j][i]);
            }
        }
    }
    ll sum = c[1] + c[2] + c[3];
    if(sum){
        for(ll i = 1;i<=3;i++){
            if(c[i]!=1&&(cnt[i]!=0)) return -1;
        }
    }
    if(s.size()>1) return -1;
    if(s.size()) ans+=2*(*s.begin());
	return ans;
}
/**
6 3
ATACAT ACTATA
1 3
4 5
3 5

5 3
ATATTA AATATT
1 4
1 2
1 6
**/

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