Submission #440094

#	Time	Username	Problem	Language	Result	Execution time	Memory
440094		ala2	Mutating DNA (IOI21_dna)	C++17	84 / 100	1571 ms	4040 KiB

dna

#include "dna.h"
#include <iostream>
#include<map>
//#include<pair>
using namespace std;
string s="",c="";
map<pair<char,char>,int>m;  int a2[1001000];  int b2[1001000];  int ca[1000100]; int ct[1000100];  int ff;
void init(string a, string b) {
    s=a;
    c=b;  int n=s.size();
    ff=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='C'||c[i]=='C')
            ff=1;
    }
        int g=0;  int A=0,T=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]!=c[i])
            {g++;   if(s[i]=='A') A++;  else T++; }
        a2[i]=g;
        ca[i]=A;
        ct[i]=T;

    }

}

int get_distance(int x, int y) {

    if(ff)
    {



    m[{'C','T'}]=0;
    m[{'T','C'}]=0;
    m[{'A','T'}]=0;
    m[{'T','A'}]=0;
    m[{'C','A'}]=0;
    m[{'A','C'}]=0;
   int A=0,C=0,T=0,A2=0,C2=0,T2=0;  int ans=0;
   for(int i=x;i<=y;i++)
   {
       if(s[i]!=c[i])
       {
           m[{s[i],c[i]}]++;  ans++;
       }
       if(s[i]=='A') A++;
       if(s[i]=='T') T++;
       if(s[i]=='C') C++;
       if(c[i]=='A') A2++;
       if(c[i]=='T') T2++;
       if(c[i]=='C') C2++;
   }  int we=0;
   if(A!=A2||C!=C2||T!=T2)
    return -1;
   else
   {
       int mn=min(m[{'A','T'}],m[{'T','A'}]); //   cout<<"         "<<mn<<endl;
       ans-=mn*2;  we+=mn;  m[{'A','T'}]-=mn;   m[{'T','A'}]-=mn;
       mn=min(m[{'A','C'}],m[{'C','A'}]);     //cout<<"         "<<mn<<endl;
         ans-=mn*2;  we+=mn;  m[{'A','C'}]-=mn;  m[{'C','A'}]-=mn;
         mn=min(m[{'T','C'}],m[{'C','T'}]);   // cout<<"         "<<mn<<endl;
         m[{'T','C'}]-=mn; m[{'C','T'}]-=mn;  //cout<<endl; cout<<endl;
         ans-=mn*2;  we+=mn;
         int h=m[{'A','T'}];
         h=max(h,m[{'T','A'}]);
         h=max(h,m[{'A','C'}]);
         h=max(h,m[{'C','A'}]);
         h=max(h,m[{'T','C'}]);
         h=max(h,m[{'C','T'}]);
         we+=h*2;

   }   m.clear();
return we;
    }

    else
    {

           int m=a2[y]-a2[x]+(s[x]!=c[x]);  int q1=0,q2=0;
   if(x==0)
   {
       q1=ca[y];
       q2=ct[y];
   }
   else
   {
       q1=ca[y]-ca[x-1];
       q2=ct[y]-ct[x-1];
   }
   if(q1!=q2) return -1;
   else
   return m/2;





    }




	return 0;
}
//   ATCTCAA   TATCATC

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