Submission #479662

#	Time	Username	Problem	Language	Result	Execution time	Memory
479662		stefantaga	Mutating DNA (IOI21_dna)	C++17	56 / 100	181 ms	11548 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;
        }
    }
    if (y-x<=2)
    {
        int scad;
        if (x==0)
        {
            scad=0;
        }
        else
        {
            scad=sum[x-1];
        }
        int val=sum[y]-scad;
        if (val==0)
        {
            return val;
        }
        return val-1;
    }
    else
    {
        int ceau1,ceau2;
        if (x==0)
        {
            ceau1=caterinca[y][1][2];
            ceau2=caterinca[y][2][1];
        }
        else
        {
            ceau1=caterinca[y][1][2]-caterinca[x-1][1][2];
            ceau2=caterinca[y][2][1]-caterinca[x-1][2][1];
        }
        if (ceau1!=ceau2)
        {
            return -1;
        }
        return ceau1;
    }
}

/*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);
      |                      ^

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