제출 #485647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485647		MilosMilutinovic	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	37 ms	7368 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=101000;
const char c[3]={'A','T','C'};
int pref[N][3][3],cnt[3][3];

void init(string a,string b) {
	int n=SZ(a);
	rep(i,0,n) rep(p,0,3) rep(q,0,3) pref[i][p][q]=pref[i-1][p][q]+(a[i]==c[p]&&b[i]==c[q]);
}

int get_distance(int l,int r) {
	VI sx(3),sy(3);
	rep(i,0,3) rep(j,0,3) {
		int occ=pref[r][i][j]-(l>0?pref[l-1][i][j]:0);
		cnt[i][j]=occ; sx[i]+=occ; sy[j]+=occ;
	}
	rep(i,0,3) if (sx[i]!=sy[i]) return -1;
	int ans=0;
	rep(i,0,3) rep(j,i+1,3) {
		int ft=min(cnt[i][j],cnt[j][i]);
		ans+=ft; cnt[i][j]-=ft; cnt[j][i]-=ft;
	}
	int ost=0;
	rep(i,0,3) rep(j,0,3) if (i!=j) ost+=cnt[i][j];
	return ans+ost*2/3;
}

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