Submission #780096

#TimeUsernameProblemLanguageResultExecution timeMemory
780096LyricallyMutating DNA (IOI21_dna)C++17
35 / 100
39 ms8500 KiB
#include<bits/stdc++.h> #include "dna.h" using namespace std; #define pii pair<int,int> #define pb push_back #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) int pre[100005][6]; int acta[100005][3],actb[100005][3]; int n; char trans(char p) { return p=='A'?'a':(p=='C'?'b':'c'); } void init(string a,string b) { a=" "+a;b=" "+b; n=(int)a.size()-1; rep1(i,n) { a[i]=trans(a[i]); b[i]=trans(b[i]); } rep1(i,n) { rep(j,6){pre[i][j]=pre[i-1][j];} rep(j,3){acta[i][j]=acta[i-1][j];} acta[i][a[i]-'a']++; rep(j,3){actb[i][j]=actb[i-1][j];} actb[i][b[i]-'a']++; if(a[i]==b[i]){continue;} if(a[i]=='a'&&b[i]=='b'){pre[i][0]++;} if(a[i]=='a'&&b[i]=='c'){pre[i][1]++;} if(a[i]=='b'&&b[i]=='a'){pre[i][2]++;} if(a[i]=='b'&&b[i]=='c'){pre[i][3]++;} if(a[i]=='c'&&b[i]=='a'){pre[i][4]++;} if(a[i]=='c'&&b[i]=='b'){pre[i][5]++;} } } int get_distance(int x,int y) { x++,y++; rep(i,3) { if(acta[y][i]-acta[x-1][i]!=actb[y][i]-actb[x-1][i]) { return -1; } } int npre[6]; rep(i,6) { npre[i]=pre[y][i]-pre[x-1][i]; } int act=npre[0]+npre[2]-2*min(npre[0],npre[2]); if(act==0) { return npre[1]; } return act*2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...