Submission #1140826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140826		hxano	Mutating DNA (IOI21_dna)	C++20	100 / 100	34 ms	6920 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define ll int
#define ii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define lwb lower_bound
#define upb upper_bound
#define ld double
#define ins insert
#define del erase
#define ull unsigned long long
using namespace std;
const ll big=2e5+9;
const ll inf=1e11;
const ll mod=1e9+7;
struct tr{ll fi,se,th; tr(ll _fi=0, ll _se=0, ll _th=0){fi=_fi; se=_se; th=_th;}};
struct qu{ll fi,se,th,fo; qu(ll _fi=0, ll _se=0, ll _th=0, ll _fo=0){fi=_fi; se=_se; th=_th; fo=_fo;}};
ll mxz(ll &t, ll val){if (t<val){t=val; return 1;} return 0;}
ll mnz(ll &t, ll val){if (t>val){t=val; return 1;} return 0;}
ll qpw(ll n, ll k, ll m=mod){ll p=1, t=n%m; while (k){if (k&1) p=p*t%m; t=t*t%m; k>>=1;} return p;}
ll n,q;
ll c[big][3][3];
ll A[big], B[big];
void init(string a, string b){
	n=(ll)a.size();
	for (ll i=0; i<n; ++i) A[i+1]=(a[i]=='A'? 0ll: (a[i]=='T'? 1ll: 2ll));
	for (ll i=0; i<n; ++i) B[i+1]=(b[i]=='A'? 0ll: (b[i]=='T'? 1ll: 2ll));
	for (ll i=1; i<=n; ++i){
		for (ll u=0; u<3; ++u) for (ll v=0; v<3; ++v) c[i][u][v]=c[i-1][u][v];
		++c[i][A[i]][B[i]];
	}
	return;
}
ll d[3][3];
int get_distance(int x, int y){
	++x; ++y;
	ll sol=0;
	for (ll u=0; u<3; ++u) for (ll v=0; v<3; ++v) if (u!=v){
		d[u][v]=c[y][u][v]-c[x-1][u][v];
	}
	for (ll u=0; u<3; ++u){
		ll ca=0, cb=0;
		for (ll v=0; v<3; ++v){
			ca+=d[u][v];
			cb+=d[v][u];
		}
		if (ca!=cb) return -1;
	}
	for (ll u=0; u<3; ++u) for (ll v=u+1; v<3; ++v){
		ll t=min(d[u][v],d[v][u]);
		d[u][v]-=t;
		d[v][u]-=t;
		sol+=t;
	}
	ll s=0;
	for (ll u=0; u<3; ++u) for (ll v=0; v<3; ++v) s+=d[u][v];
	if (s%3) return -1;
	sol+=s/3*2;
	return sol;
}
ll solve(){
	cin>>n>>q;
	string a,b;
	cin>>a>>b;
	init(a,b);
	for (; q; --q){
		ll x,y; cin>>x>>y;
//		for (ll i=x; i<=y; ++i) cout<<a[i]; cout<<" ";
//		for (ll i=x; i<=y; ++i) cout<<b[i]; cout<<": ";
		cout<<get_distance(x,y)<<"\n";
	}
	return 0;
}
int mainn(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("INPUT.TXT","r",stdin);
    freopen("OUTPUT.TXT","w",stdout);
	ll tst=1;
//	cin>>tst;
	for (; tst; --tst) solve();
    return 0;
}

Compilation message (stderr)

dna.cpp:17:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+11' to '2147483647' [-Woverflow]
   17 | const ll inf=1e11;
      |              ^~~~
dna.cpp: In function 'int mainn()':
dna.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen("INPUT.TXT","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen("OUTPUT.TXT","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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