Submission #955185

#TimeUsernameProblemLanguageResultExecution timeMemory
955185IUA_HasinMutating DNA (IOI21_dna)C++17
0 / 100
80 ms11544 KiB
#include <bits/stdc++.h> #define endl "\n" #define finp for(int i=0; i<n; i++) #define fknp for(int k=0; k<n; k++) #define yeap cout<<"YES"<<endl #define nope cout<<"NO"<<endl #define inpintn int n; cin>>n #define inpintarrn int arr[n]; for(int i=0; i<n; i++){cin>>arr[i];} #define inpllarrn long long arr[n]; for(int i=0; i<n; i++){cin>>arr[i];} #define ll long long using namespace std; #include "dna.h" ll const N = 1e5+10; string aa, bb; ll arra[N], arrc[N], arrt[N]; ll brra[N], brrc[N], brrt[N]; ll diff[N], diff2[N]; ll ccnt[N]; void init(std::string a, std::string b) { aa = a; bb = b; ll siz = a.size(); for(int i=0; i<siz; i++){ if(a[i]=='A'){ arra[i+1] = arra[i]+1; arrc[i+1] = arrc[i]; arrt[i+1] = arrt[i]; } else if(a[i]=='C'){ arra[i+1] = arra[i]; arrc[i+1] = arrc[i]+1; arrt[i+1] = arrt[i]; } else { arra[i+1] = arra[i]; arrc[i+1] = arrc[i]; arrt[i+1] = arrt[i]+1; } if(b[i]=='A'){ brra[i+1] = brra[i]+1; brrc[i+1] = brrc[i]; brrt[i+1] = brrt[i]; } else if(b[i]=='C'){ brra[i+1] = brra[i]; brrc[i+1] = brrc[i]+1; brrt[i+1] = brrt[i]; } else { brra[i+1] = brra[i]; brrc[i+1] = brrc[i]; brrt[i+1] = brrt[i]+1; } } for(int i=0; i<siz; i++){ char p = aa[i]; char q = bb[i]; if(p!=q){ diff[i+1] = diff[i]+1; } else { diff[i+1] = diff[i]; } } for(int i=0; i<siz; i++){ char p = aa[i]; char q = bb[i]; if(p!=q){ if(p!='C' && q!='C'){ diff2[i+1] = diff2[i]+1; } else { diff2[i+1] = diff2[i]; } } else { diff2[i+1] = diff2[i]; } } for(int i=0; i<siz; i++){ char p = aa[i]; char q = bb[i]; if(p=='C' && p==q){ ccnt[i+1] = ccnt[i]+1; } else { ccnt[i+1] = ccnt[i]; } } } int get_distance(int x, int y) { x = x+1; y = y+1; // ll siz1 = aa.size(); // ll diff[siz1+1]; // diff[0] = 0; // for(int i=0; i<siz1; i++){ // char p = aa[i]; // char q = bb[i]; // if(p!=q){ // diff[i+1] = diff[i]+1; // } else { // diff[i+1] = diff[i]; // } // } ll xa = arra[y]-arra[x-1]; ll xc = arrc[y]-arrc[x-1]; ll xt = arrt[y]-arrt[x-1]; ll ya = brra[y]-brra[x-1]; ll yc = brrc[y]-brrc[x-1]; ll yt = brrt[y]-brrt[x-1]; ll d = diff[y]-diff[x-1]; ll d2 = diff2[y]-diff2[x-1]; ll cc = ccnt[y]-ccnt[x-1]; cout << xa << " " << xc << " " << xt << " " << ya << " " << yc << " " << yt << " " << d << " " << d2 << " " << cc << endl; if(y-x<=2){ if(xa==ya && xc==yc && xt==yt){ if(d==0){ return 0; } else if(d==2){ return 1; } else { return 2; } } else { return -1; } } else { if(xa==ya && xc==yc && xt==yt){ if(xa==0 || xc==0 || xt==0){ ll ans = d/2; return ans; } else { if(d2%2==0){ ll fx = d2/2; ll gx = d-fx*2-xc+cc; ll ans = fx+gx; // cout << fx << " " << gx << " " << ans << endl; return ans; } else { ll fx = floor(d2/2); ll gx = d-fx*2-xc+cc; ll ans = fx+gx; // cout << fx << " " << gx << " " << ans << endl; return ans; } } } else { return -1; } } }
#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...