Submission #440142

#	Time	Username	Problem	Language	Result	Execution time	Memory
440142		ala2	Mutating DNA (IOI21_dna)	C++17	100 / 100	158 ms	8880 KiB

dna

#include "dna.h"
#include <iostream>
#include<map>
//#include<pair>
using namespace std; int ct[1000100],tc[1000100],att[1000100],ta[1001000],ca[1000100],ac[1001000];
int AA[1000100],CC[1000100],TT[1001000];  int AA2[1000100],CC2[1000100],TT2[1001000];
string s="",c="";
map<pair<char,char>,int>m;
void init(string a, string b) {
    s=a;
    c=b;  int n=s.size();
    ct[0]=(s[0]=='C'&&c[0]=='T');
    tc[0]=(s[0]=='T'&&c[0]=='C');
    att[0]=(s[0]=='A'&&c[0]=='T');
    ta[0]=(s[0]=='T'&&c[0]=='A');
    ac[0]=(s[0]=='A'&&c[0]=='C');
    ca[0]=(s[0]=='C'&&c[0]=='A');
    for(int i=1;i<n;i++)
    {
    ct[i]=ct[i-1]+(s[i]=='C'&&c[i]=='T');
    tc[i]=(s[i]=='T'&&c[i]=='C')+tc[i-1];
    att[i]=(s[i]=='A'&&c[i]=='T')+att[i-1];
    ta[i]=(s[i]=='T'&&c[i]=='A')+ta[i-1];
    ac[i]=(s[i]=='A'&&c[i]=='C')+ac[i-1];
    ca[i]=(s[i]=='C'&&c[i]=='A')+ca[i-1];
    }

    int aa=0,cc=0,tt=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='A')
            aa++;
        if(s[i]=='T')
            tt++;
        if(s[i]=='C')
            cc++;
        AA[i]=aa;
        CC[i]=cc;
        TT[i]=tt;
    }


    int aa2=0,cc2=0,tt2=0;
    for(int i=0;i<n;i++)
    {
        if(c[i]=='A')
            aa2++;
        if(c[i]=='T')
            tt2++;
        if(c[i]=='C')
            cc2++;
        AA2[i]=aa2;
        CC2[i]=cc2;
        TT2[i]=tt2;
    }



}

int get_distance(int x, int y) {
    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;


    if(x>0)
    {
        A=AA[y]-AA[x-1];
        C=CC[y]-CC[x-1];
        T=TT[y]-TT[x-1];

        A2=AA2[y]-AA2[x-1];
        C2=CC2[y]-CC2[x-1];
        T2=TT2[y]-TT2[x-1];

    m[{'C','T'}]=ct[y]-ct[x-1];
    m[{'T','C'}]=tc[y]-tc[x-1];
    m[{'A','T'}]=att[y]-att[x-1];
    m[{'T','A'}]=ta[y]-ta[x-1];
    m[{'C','A'}]=ca[y]-ca[x-1];
    m[{'A','C'}]=ac[y]-ac[x-1];
    }
    else
    {
        A=AA[y];
        C=CC[y];
        T=TT[y];

        A2=AA2[y];
        C2=CC2[y];
        T2=TT2[y];



            m[{'C','T'}]=ct[y];
    m[{'T','C'}]=tc[y];
    m[{'A','T'}]=att[y];
    m[{'T','A'}]=ta[y];
    m[{'C','A'}]=ca[y];
    m[{'A','C'}]=ac[y];
    }




int we=0;

    int ans=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;

	return 0;
}
//   ATCTCAA   TATCATC

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