Submission #479667

#	Time	Username	Problem	Language	Result	Execution time	Memory
479667		stefantaga	Mutating DNA (IOI21_dna)	C++17	100 / 100	207 ms	11728 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>
using namespace std;
vector <int> poza[5],pozb[5];
int n,sum[100005],val[505];
int caterinca[100005][4][4];
void init (string a,string b)
{
    n=a.size();
    val['A']=1;
    val['T']=2;
    val['C']=3;
    for (int i=0; i<a.size(); i++)
    {
        if (i==0)
        {
            sum[i]=(a[i]!=b[i]);
        }
        else
        {
            sum[i]=sum[i-1]+(a[i]!=b[i]);
        }
        if (i>0)
        {
            for (int t=1; t<=3; t++)
            {
                for (int k=1; k<=3; k++)
                {
                    caterinca[i][t][k]=caterinca[i-1][t][k];
                }
            }
        }
        caterinca[i][val[a[i]]][val[b[i]]]++;
        poza[val[a[i]]].push_back(i);
        pozb[val[b[i]]].push_back(i);
    }
}
int cautsta(int loc,int poz)
{
    int st=0,dr=(int)poza[loc].size()-1,mij;
    int sol=poza[loc].size();
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (poza[loc][mij]>=poz)
        {
            sol=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return sol;
}
int cautstb(int loc,int poz)
{
    int st=0,dr=(int)pozb[loc].size()-1,mij;
    int sol=pozb[loc].size();
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (pozb[loc][mij]>=poz)
        {
            sol=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return sol;
}
int cautdra(int loc,int poz)
{
    int st=0,dr=(int)poza[loc].size()-1,mij;
    int sol=-1;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (poza[loc][mij]<=poz)
        {
            sol=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return sol;
}
int cautdrb(int loc,int poz)
{
    int st=0,dr=(int)pozb[loc].size()-1,mij;
    int sol=-1;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (pozb[loc][mij]<=poz)
        {
            sol=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return sol;
}
int get_distance(int x,int y)
{
    for (int i=1; i<=3; i++)
    {
        int sta,stb,dra,drb;
        sta=cautsta(i,x);
        stb=cautstb(i,x);
        dra=cautdra(i,y);
        drb=cautdrb(i,y);
        if (dra-sta!=drb-stb)
        {
            return -1;
        }
    }
    int bonjour[4][4],sum=0,i,j;
    for (i=1; i<=3; i++)
    {
        for (j=1; j<=3; j++)
        {
            if (i!=j)
            {
                if (x==0)
                {
                    bonjour[i][j]=caterinca[y][i][j];
                    bonjour[j][i]=caterinca[y][j][i];
                }
                else
                {
                    bonjour[i][j]=caterinca[y][i][j]-caterinca[x-1][i][j];
                    bonjour[j][i]=caterinca[y][j][i]-caterinca[x-1][j][i];
                }
            }
        }
    }
    for (i=1;i<=3;i++)
    {
        for (j=1;j<=3;j++)
        {
            if (i!=j)
            {
                int val=min(bonjour[i][j],bonjour[j][i]);
                sum=sum+val;
                bonjour[i][j]-=val;
                bonjour[j][i]-=val;
            }
        }
    }
    int ok=0,sum2=0;
    for (i=1;i<=3;i++)
    {
        for (j=1;j<=3;j++)
        {
            if (i!=j&&bonjour[i][j]!=0)
            {
                sum2=sum2+bonjour[i][j];
            }
        }
    }
    sum=sum+2*sum2/3;
    return sum;
}

/*int main() {
	int n, q;
	assert(scanf("%d %d", &n, &q) == 2);
	char A[n+1], B[n+1];
	assert(scanf("%s", A) == 1);
	assert(scanf("%s", B) == 1);
	std::string a = std::string(A);
	std::string b = std::string(B);
	std::vector<int> x(q), y(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);
	std::vector<int> results(q);
	init(a, b);
	for (int i = 0; i < q; i++) {
		results[i] = get_distance(x[i], y[i]);
	}
	for (int i = 0; i < q; i++) {
		printf("%d\n", results[i]);
	}
	fclose(stdout);
	return 0;
}*/

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i=0; i<a.size(); i++)
      |                   ~^~~~~~~~~
dna.cpp:37:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |         caterinca[i][val[a[i]]][val[b[i]]]++;
      |                              ^
dna.cpp:37:41: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |         caterinca[i][val[a[i]]][val[b[i]]]++;
      |                                         ^
dna.cpp:38:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |         poza[val[a[i]]].push_back(i);
      |                      ^
dna.cpp:39:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |         pozb[val[b[i]]].push_back(i);
      |                      ^
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:165:9: warning: unused variable 'ok' [-Wunused-variable]
  165 |     int ok=0,sum2=0;
      |         ^~

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