Submission #630662

#	Time	Username	Problem	Language	Result	Execution time	Memory
630662		tmncollins	Mutating DNA (IOI21_dna)	C++17	100 / 100	59 ms	10408 KiB

dna

#include <string>
#include <array>
#include <map>
#include <fstream>
#include <iostream>

using namespace std;

string A, B;
const int SIZE = 100005;
const int MAT_SIZE = 4;

struct base_info {
    int arr[MAT_SIZE][MAT_SIZE];

    base_info() {
        for (int k = 0; k < MAT_SIZE; k++) {
            for (int i = 0; i < MAT_SIZE; i++) {
                arr[i][k] = 0;
            }
        }
    }

    base_info operator+ (const base_info &d) const {
        base_info ret;

        for (int k = 0; k < MAT_SIZE; k++) {
            for (int i = 0; i < MAT_SIZE; i++) {
                ret.arr[k][i] = d.arr[k][i] + arr[k][i];
            }
        }

        return ret;
    }

    base_info& operator+= (const base_info &d) {

        for (int k = 0; k < MAT_SIZE; k++) {
            for (int i = 0; i < MAT_SIZE; i++) {
                arr[k][i] += d.arr[k][i];
            }
        }

        return *this;
    }

    base_info operator- (const base_info &d) const {
        base_info ret;

        for (int k = 0; k < MAT_SIZE; k++) {
            for (int i = 0; i < MAT_SIZE; i++) {
                ret.arr[k][i] = -d.arr[k][i] + arr[k][i];
            }
        }

        return ret;
    }

    base_info& operator-= (const base_info &d) {
        for (int k = 0; k < MAT_SIZE; k++) {
            for (int i = 0; i < MAT_SIZE; i++) {
                arr[k][i] -= d.arr[k][i];
            }
        }
        return *this;
    }

    int swap_d() const {
        int tot = 0;
        int spare[MAT_SIZE];

        for (int i = 0; i < MAT_SIZE; i++) {
            spare[i] = 0;
        }

        // count all of the bases
        for (int k = 0; k < MAT_SIZE; k++) {
            for (int i = 0; i < MAT_SIZE; i++) {
                tot += arr[k][i];
                spare[k] += arr[k][i];
                spare[i] -= arr[k][i];
            }
        }

        // check if any numbers are unpaired
        for (int k = 0; k < MAT_SIZE; k++) {
            if (spare[k]) return -1;
        }

        base_info d = *this;
        int same = 0;

        // count the number of bases that are in the right place
        for (int k = 0; k < MAT_SIZE; k++) {
            same += d.arr[k][k];
            d.arr[k][k] = 0;
        }

        int cycle_swaps = 0;

        // check how many ways we can directly swap (as a 2)
        for (int k = 0; k < MAT_SIZE; k++) {
            for (int i = 0; i < k; i++) {
                int s = min(d.arr[k][i], d.arr[i][k]);
                cycle_swaps += s;
                d.arr[i][k] -= s;
                d.arr[k][i] -= s;
            }
        }

        // count how many ways we can swap in a cycle (of 3)
        for (int a = 0; a < MAT_SIZE; a++) {
            for (int b = 0; b < a; b++) {
                for (int c = 0; c < b; c++) {
                    int s;
                    s = min(d.arr[a][b], min(d.arr[b][c], d.arr[c][a]));
                    cycle_swaps += s;
                    d.arr[a][b] -= s;
                    d.arr[b][c] -= s;
                    d.arr[c][a] -= s;

                    s = min(d.arr[b][a], min(d.arr[a][c], d.arr[c][b]));
                    cycle_swaps += s;
                    d.arr[b][a] -= s;
                    d.arr[a][c] -= s;
                    d.arr[c][b] -= s;
                }
            }
        }

        // count the number of remaining bases
        // this should be 0
        int unpaired = 0;
        for (int k = 0; k < MAT_SIZE; k++) {
            for (int i = 0; i < MAT_SIZE; i++) {
                unpaired += d.arr[k][i];
            }
        }
        unpaired /= 4;

        return tot - same - unpaired - cycle_swaps;

    }
};

map<char, int> bases;
base_info prefix[SIZE];

void init(string a, string b) {
    A = a;
    B = b;

    bases['A'] = 0;
    bases['G'] = 1;
    bases['T'] = 2;
    bases['C'] = 3;

    base_info d;
    for (int k = 0; k < a.size(); k++) {
        int i = bases[a[k]], j = bases[b[k]];
        d.arr[i][j] = 1;
        prefix[k+1] += d;
        prefix[k+1] += prefix[k];
        d.arr[i][j] = 0;
    }



}

int get_distance(int x, int y) {
    base_info b = prefix[y+1] - prefix[x];
    return b.swap_d();
}

Compilation message (stderr)

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

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