Submission #437523

#TimeUsernameProblemLanguageResultExecution timeMemory
437523Sho10Mutating DNA (IOI21_dna)C++17
0 / 100
46 ms7236 KiB
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho #define ll int #define double long double #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #define aint(a) (a).begin(), (a).end() #define f first #define s second #define pb push_back #define mp make_pair #define pi pair #define rc(s) return cout<<s,0 #define endl '\n' #define mod 1000000007 #define PI 3.14159265359 #define INF 1000000005 #define LINF 1000000000000000005ll #define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; string a,b; ll n,cnt[7][1000005],viz[3][4][1000005]; void init(string A,string B){ a=A; b=B; n=a.size(); a=" "+a; b=" "+b; for(ll i=1;i<=n;i++) { for(ll j=1;j<=3;j++) { viz[1][j][i]=viz[1][j][i-1]; viz[2][j][i]=viz[2][j][i-1]; } if(a[i]=='A'){ viz[1][1][i]++; }else if(a[i]=='C'){ viz[1][2][i]++; }else if(a[i]=='T'){ viz[1][3][i]++; } if(b[i]=='A'){ viz[2][1][i]++; }else if(b[i]=='C'){ viz[2][2][i]++; }else if(b[i]=='T'){ viz[2][3][i]++; } for(ll j=1;j<=6;j++) { cnt[j][i]=cnt[j][i-1]; } if(a[i]=='A'&&b[i]=='C'){ cnt[1][i]++; }else if(a[i]=='A'&&b[i]=='T'){ cnt[2][i]++; }else if(a[i]=='C'&&b[i]=='T'){ cnt[3][i]++; }else if(a[i]=='C'&&b[i]=='A'){ cnt[4][i]++; }else if(a[i]=='T'&&b[i]=='A'){ cnt[5][i]++; }else { cnt[6][i]++; } } return; } int get_distance(int x,int y){ x++; y++; for(ll j=1;j<=3;j++) { if(viz[1][j][y]-viz[1][j][x-1]!=viz[2][j][y]-viz[2][j][x-1]){ return -1; } } ll ans=0; ll mn=INF; ll s[7]; for(ll j=1;j<=6;j++) { s[j]=cnt[j][y]-cnt[j][x-1]; } mn=min(s[1],s[4]); ans+=mn; s[1]-=mn; s[4]-=mn; mn=min(s[2],s[5]); ans+=mn; s[2]-=mn; s[5]-=mn; mn=min(s[3],s[6]); ans+=mn; s[3]-=mn; s[6]-=mn; ans+=(s[1]+s[2]+s[3]+s[4]+s[5]+s[6])/3*2; return ans; }
#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...