Submission #970546

#	Time	Username	Problem	Language	Result	Execution time	Memory
970546		NemanjaSo2005	Mutating DNA (IOI21_dna)	C++17	100 / 100	42 ms	23216 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int mapa[130],N,v;
struct slog{
   int kol[5][5];
   slog operator + (const slog &a) const{
      slog ret;
      for(int i=0;i<=2;i++)
         for(int j=0;j<=2;j++)
            ret.kol[i][j]=kol[i][j]+a.kol[i][j];
      return ret;
   }
   slog operator - (const slog &a) const{
      slog ret;
      for(int i=0;i<=2;i++)
         for(int j=0;j<=2;j++)
            ret.kol[i][j]=kol[i][j]-a.kol[i][j];
      return ret;
   }
   void ispisi(){
      for(int i=0;i<=2;i++){
         for(int j=0;j<=2;j++)
            cout<<kol[i][j]<<" ";
         cout<<endl;
      }
   }
} niz[100005],prefiks[100005],tr;
void init(string a, string b){
   mapa['A']=0;
   mapa['T']=1;
   mapa['C']=2;
   N=a.size();
   a="."+a+"....";
   b="."+b+"....";
   for(int i=1;i<=N;i++)
      niz[i].kol[mapa[a[i]]][mapa[b[i]]]++;
   for(int i=1;i<=N;i++)
      prefiks[i]=prefiks[i-1]+niz[i];
  // for(int i=1;i<=N;i++){
     // cout<<i<<endl;
     // prefiks[i].ispisi();
   //}
   return;
}
bool nemoze(slog tr){
   ll vr=0;
   for(int i=0;i<=2;i++){
      vr+=tr.kol[0][i];
      vr-=tr.kol[i][0];
   }
   if(vr!=0)
      return true;
   for(int i=0;i<=2;i++){
      vr+=tr.kol[1][i];
      vr-=tr.kol[i][1];
   }
   if(vr!=0)
      return true;
   for(int i=0;i<=2;i++){
      vr+=tr.kol[2][i];
      vr-=tr.kol[i][2];
   }
   if(vr!=0)
      return true;
   return false;
}
int get_distance(int x, int y){
   x++;
   y++;
   ll ret=0;
   tr=prefiks[y]-prefiks[x-1];
  // cout<<"QUERY "<<x<<" "<<y<<endl;
  // tr.ispisi();
   if(nemoze(tr))
      return -1;
   tr.kol[0][0]=tr.kol[1][1]=tr.kol[2][2]=0;
   //tr.ispisi();
   int i,j;

   i=0;j=1;
   v=min(tr.kol[i][j],tr.kol[j][i]);
   ret+=v;
   tr.kol[i][j]-=v;
   tr.kol[j][i]-=v;
  // cout<<v<<endl;

   i=0;j=2;
   v=min(tr.kol[i][j],tr.kol[j][i]);
   ret+=v;
   tr.kol[i][j]-=v;
   tr.kol[j][i]-=v;
   //cout<<v<<endl;

   i=1;j=2;
   v=min(tr.kol[i][j],tr.kol[j][i]);
   ret+=v;
   tr.kol[i][j]-=v;
   tr.kol[j][i]-=v;
   //cout<<v<<endl;
   v=0;
   for(i=0;i<=2;i++)
      for(j=0;j<=2;j++){
         v+=tr.kol[i][j];
      }
   return ret+(v*2)/3;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:38:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |       niz[i].kol[mapa[a[i]]][mapa[b[i]]]++;
      |                           ^
dna.cpp:38:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |       niz[i].kol[mapa[a[i]]][mapa[b[i]]]++;
      |                                       ^

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