Submission #497415

#	Time	Username	Problem	Language	Result	Execution time	Memory
497415		Maqsut_03	Mutating DNA (IOI21_dna)	C++17	0 / 100	680 ms	49952 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++){
        dp[i+1][a1[i]-'A']+=dp[i][a1[i]-'A']+1;
        dp1[i+1][b1[i]-'A']+=dp1[i][a1[i]-'A']+1;
    }
    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();
   for (int i = 0; i < 26; 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])+((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:42:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |     if (a.size() > y-x+1) a = a.substr(x, y);
      |         ~~~~~~~~~^~~~~~~
dna.cpp:43:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     if (b.size() > y-x+1) b = b.substr(x, y);
      |         ~~~~~~~~~^~~~~~~

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