Submission #448577

#	Time	Username	Problem	Language	Result	Execution time	Memory
448577		julian33	Mutating DNA (IOI21_dna)	C++17	56 / 100	41 ms	7420 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=1e5+5; //make sure this is right
const int mod=1e9+7;

int f[mxN][3][2],id[1000],n,cnt[mxN][3];

void init(string a,string b){
    id['A']=0;
    id['C']=1;
    id['T']=2;
    n=sz(a);
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            if(id[a[i-1]]==j)
                f[i][j][0]=f[i-1][j][0]+1;
            else
                f[i][j][0]=f[i-1][j][0];
            if(id[b[i-1]]==j)
                f[i][j][1]=f[i-1][j][1]+1;
            else
                f[i][j][1]=f[i-1][j][1];
            cnt[i][j]+=cnt[i-1][j];
        }
        if(minmax({a[i-1],b[i-1]})==minmax({'A','C'}))
            cnt[i][0]++;
        else if(minmax({a[i-1],b[i-1]})==minmax({'A','T'}))
            cnt[i][1]++;
        else if(minmax({a[i-1],b[i-1]})==minmax({'C','T'}))
            cnt[i][2]++;
    }
}

int get_distance(int x,int y){
    y++;
    for(int i=0;i<3;i++){
        if(f[y][i][0]-f[x][i][0]!=f[y][i][1]-f[x][i][1])
            return -1;
    }
    int a1=cnt[y][0]-cnt[x][0];
    int a2=cnt[y][1]-cnt[x][1];
    int a3=cnt[y][2]-cnt[x][2];
    int ans=0;
    int m=min(a1,a2);
    ans+=m;
    a1-=m;
    ans+=a1/2+(a2+a3)/2;
    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:41:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |             if(id[a[i-1]]==j)
      |                         ^
dna.cpp:45:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |             if(id[b[i-1]]==j)
      |                         ^

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