제출 #1111899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111899		Zflop	DNA 돌연변이 (IOI21_dna)	C++17	35 / 100	26 ms	6940 KiB

dna

#include <bits/stdc++.h>
using namespace std;
const int NMAX = (int)1e5 * 2;
int sum[NMAX][3][3],N;

int get (char a) {
    if (a == 'A') return 0;
    if (a == 'C') return 1;
    return 2;
}

void init(std::string a, std::string b) {
    N = a.size();
    for (int i = 1; i <= N;++i) {
        for (int x = 0; x < 3;++x)
            for (int y = 0; y < 3;++y)
                sum[i][x][y] += sum[i - 1][x][y];
        sum[i][get(a[i - 1])][get(b[i - 1])]++;
    }
}
int get_distance(int x, int y) {
    ++x,++y;
    int ans = 0;
    vector<vector<int>>v;
    set<int>m;
    int r = 0;
    for (int a = 0; a < 3;++a)
        for (int b = a + 1; b < 3;++b) {
            int one = sum[y][a][b] - sum[x - 1][a][b];
            int two = sum[y][b][a] - sum[x - 1][b][a];
            int g = min(one,two);
            r += one + two;
            if (g != max(one,two)) {
                if(one > two) {
                    v.push_back({a,b,one - two});
                    m.insert(a);
                }
                else  {
                    v.push_back({b,a,two - one});
                    m.insert(b);
                }
            }
            ans += g;
        }
    if (v.size() == 0) return ans;
    if (v.size() == 1) return -1;

    if (v.size() == 2) {
        if (v[0][0] != v[1][1] || v[0][2] != v[1][2]) return -1;
        return ans + v[0][2];
    }
    if (v.size() == 3) {
        sort(v.begin(),v.end(),[&](vector<int>a,vector<int>b) {return a[2] < b[2];});
        return r / 3;
        if(m.size() == 3){
            ans += v[0][2] + v[1][2];
            //cout << v[0][2] << ' ' << v[1][2] << ' ' << v[2][2] << '\n';
            for (int i = 0; i < 3;++i)
                for (int j = i + 1; j < 3;++j)
                    if (v[i][0] == v[j][1] && v[i][2] != v[j][2])
                        return -1;
            return ans;
            }
        return -1;
    }
    return -1;
}

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