Submission #479666

#TimeUsernameProblemLanguageResultExecution timeMemory
479666stefantagaMutating DNA (IOI21_dna)C++17
35 / 100
193 ms10212 KiB
#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+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;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...