Submission #499934

#	Time	Username	Problem	Language	Result	Execution time	Memory
499934		MurotY	Mutating DNA (IOI21_dna)	C++17	43 / 100	1579 ms	50500 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
const long long N=1e5+7;
string a, b, a1, b1;
int n;
long long dp[N][30], dp1[N][30], p[N];
void init(string a0, string b0) {
    a = a0;
    b = b0;
    a1 = a;
    b1 = b;
    n = a.length();
   for (int i=0;i<=n;i++) {
        for (int j=0;j<=26;j++) dp[i][j]=dp1[i][j]=0;
        p[i]=0;
    }
    for (int i=0;i<n;i++){
            for (char j='A';j<='Z';j++){
                if (j == a1[i]) dp[i+1][j-'A']+=dp[i][j-'A']+1;

                else dp[i+1][j-'A']=dp[i][j-'A'];
                if (j == b1[i]) dp1[i+1][j-'A']+=dp1[i][j-'A']+1;
                else dp1[i+1][j-'A']=dp1[i][j-'A'];
  //              cout << dp[i+1][j-'A'] <<" ";
            }
//            cout <<"\n";
             if (a1[i] != b1[i]) p[i+1]+=p[i]+1;
             else p[i+1]=p[i];
    }
}
int get_distance(int x, int y) {
    int ans = 0;
    a = a1;
    b = b1;
   for (int i = 0; i < 26; i++){
            //cout << dp[y+1][i] <<" ";
            if (dp[y+1][i]-dp[x][i] != dp1[y+1][i]-dp1[x][i]) return -1;
    }

    if ((dp[y+1][0]-dp[x][0])+(dp[y+1]['T'-'A']-dp[x][0])+
        (dp1[y+1][0]-dp1[x][0])+(dp1[y+1]['T'-'A']-dp1[x]['T'-'A']) == 2*(y-x+1)){
          //  cout << 1;
         return ((p[y+1]-p[x])/2)+((p[y+1]-p[x]) % 2);
    }

    if (a.size() > y-x+1) a = a.substr(x, y);
    if (b.size() > y-x+1) b = b.substr(x, y);
    for (int i=0;i<=y-x;i++){
        bool ok=0;
        for (int j=i+1;j<=y-x;j++){
            if (a[i] == b[j] and b[i] != a[i] and a[j] == b[i]){
            ok=1;
            ans++;
            swap(b[i], b[j]);
//            cout << 1;
            }
        }
        if (!ok){
            for (int j=i+1;j<=y-x;j++){
                if (a[i] == b[j] and b[i] != a[i]){
                    ans++;
                    swap(b[i], b[j]);
//                  cout << b <<" ";
                }
            }
        }
    }
    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:47:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if (a.size() > y-x+1) a = a.substr(x, y);
      |         ~~~~~~~~~^~~~~~~
dna.cpp:48:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     if (b.size() > y-x+1) b = b.substr(x, y);
      |         ~~~~~~~~~^~~~~~~

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