제출 #777045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777045		Blagoj	Mutating DNA (IOI21_dna)	C++17	84 / 100	1568 ms	6856 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

string a, b;

bool two = false;

int dp[100009], counter[100009][3][2];

map<char, int> mp;
set<char> s;

void init(std::string a1, std::string b1) {
    mp['C'] = 0;
    mp['A'] = 1;
    mp['T'] = 2;
    a = a1;
    b = b1;
    if (a[0] != b[0]) {
        dp[0] = 1;
    }
    s.insert(a[0]);
    s.insert(b[0]);
    counter[0][mp[a[0]]][0]++;
    counter[0][mp[b[0]]][1]++;
    for (int i = 1; i < a.size(); i++) {
        s.insert(a[i]);
        s.insert(b[i]);
        dp[i] = dp[i - 1];
        if (a[i] != b[i]) {
            dp[i]++;
        }
        for (int j = 0; j < 3; j++) {
            counter[i][j][0] = counter[i - 1][j][0];
            counter[i][j][1] = counter[i - 1][j][1];
        }
        counter[i][mp[a[i]]][0]++;
        counter[i][mp[b[i]]][1]++;
    }
}

int get_distance(int x, int y) {
    if (x == 0) {
        for (int i = 0; i < 3; i++) {
            if (counter[y][i][0] != counter[y][i][1]) {
                return -1;
            }
        }
    }
    else {
        for (int i = 0; i < 3; i++) {
            if ((counter[y][i][0] - counter[x - 1][i][0]) !=
                (counter[y][i][1] - counter[x - 1][i][1])) {
                return -1;
            }
        }
    }
    if (s.size() == 2) {
        if (x == 0) {
            return dp[y] / 2;
        }
        return (dp[y] - dp[x - 1]) / 2;
    }
    string c = a;
    int cnt = 0;
    for (int i = x; i <= y; i++) {
        if (c[i] != b[i]) {
            cnt++;
            for (int j = i + 1; j <= y; j++) {
                if (c[j] == b[j] || c[j] != b[i]) {
                    continue;
                }
                if (c[i] == b[j]) {
                    swap(c[i], c[j]);
                    j = y;
                }
            }
            if (c[i] != b[i]) {
                for (int j = i + 1; j <= y; j++) {
                    if (c[j] == b[j] || c[j] != b[i]) {
                        continue;
                    }
                    swap(c[i], c[j]);
                    j = y;
                }
            }
        }
    }
    return cnt;
}

컴파일 시 표준 에러 (stderr) 메시지

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 1; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~

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