Submission #479569

#	Time	Username	Problem	Language	Result	Execution time	Memory
479569		stefantaga	Mutating DNA (IOI21_dna)	C++17	0 / 100	124 ms	4820 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];
void init (string a,string b)
{
    n=a.size();
    val['A']=1;
    val['G']=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]);
        }
        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=-1;
    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=-1;
    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 scad;
    if (x==0)
    {
        scad=0;
    }
    else
    {
        scad=sum[x-1];
    }
    int val=sum[y]-scad;
    if (val==0)
    {
        return val;
    }
    return val-1;
}

/*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:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i=0;i<a.size();i++)
      |                  ~^~~~~~~~~
dna.cpp:26:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         poza[val[a[i]]].push_back(i);
      |                      ^
dna.cpp:27:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |         pozb[val[b[i]]].push_back(i);
      |                      ^

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