Submission #497402

#	Time	Username	Problem	Language	Result	Execution time	Memory
497402		Maqsut_03	Mutating DNA (IOI21_dna)	C++17	0 / 100	833 ms	44888 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;
map <char, int> arr, mp;
long long dp[N][26], dp1[N][26], 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++){
        dp[i+1][a1[i]-'A']+=dp[i][a1[i]-'A'];
        dp1[i+1][b1[i]-'A']+=dp1[i][a1[i]-'A'];
    }
    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();
    mp.clear();
 //   cout << dp[1][0] <<" ";
    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);
    }
    if ((y-x)+1 < a.size()) a=a.substr(x, y), 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:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if ((y-x)+1 < a.size()) a=a.substr(x, y), b=b.substr(x, y);
      |         ~~~~~~~~^~~~~~~~~~
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:16:51: warning: iteration 26 invokes undefined behavior [-Waggressive-loop-optimizations]
   16 |         for (int j=0;j<=26;j++) dp[i][j]=dp1[i][j]=0;
      |                                          ~~~~~~~~~^~
dna.cpp:16:23: note: within this loop
   16 |         for (int j=0;j<=26;j++) dp[i][j]=dp1[i][j]=0;
      |                      ~^~~~

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