Submission #497437

#	Time	Username	Problem	Language	Result	Execution time	Memory
497437		Maqsut_03	Mutating DNA (IOI21_dna)	C++17	43 / 100	1518 ms	51772 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];
map <char, int> arr;
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";
    }
    for (int i=0;i<n;i++){
        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;
    arr.clear();
 //  cout << dp[1][0] <<" ";

 /*  for (int i=1;i<=n;i++){
    for (int j=0;j<26;j++) cout << dp[i][j] <<" ";cout <<"\n";}*/


   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]['A'-'A']-dp[x]['T'-'A'])+ (dp1[y+1]['A'-'A']-dp1[x]['T'-'A']) == 2*(y-x+1)){
         return ((p[y+1]-p[x])/2)+((p[y+1]-p[x]) % 2);
    }
/*   for (int i=x;i<=y;i++) arr[a[i]]++, arr[b[i]]--;
    for (char i='A';i<='Z';i++) if (arr[i] != 0) return -1;*/

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