Submission #734142

#	Time	Username	Problem	Language	Result	Execution time	Memory
734142		JakobZorz	Mutating DNA (IOI21_dna)	C++17	100 / 100	43 ms	6084 KiB

dna

#include "dna.h"
#include <iostream>

int sum[100001][3][3];

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

void init(std::string a, std::string b) {
    for(int i = 0; i < (int)a.size(); i++) {
        //std::cout << get(a[i]) << " " << get(b[i]) << std::endl;
        
        for(int t1 = 0; t1 < 3; t1++) {
            for(int t2 = 0; t2 < 3; t2++) {
                sum[i + 1][t1][t2] = sum[i][t1][t2];
            }
        }
        
        sum[i + 1][get(a[i])][get(b[i])]++;
    }
}

/*
   
   0  1  2
 0 {} [] []
 1 [] {} []
 2 [] [] {}
 
    a b    b a
    b a -> b a
 
    a b c    a b c
    b c a -> a b c
 
 */

int get_distance(int x, int y) {
    int curr[3][3];
    
    for(int t1 = 0; t1 < 3; t1++) {
        for(int t2 = 0; t2 < 3; t2++) {
            curr[t1][t2] = sum[y + 1][t1][t2] - sum[x][t1][t2];
        }
    }
    
    for(int t = 0; t < 3; t++)
        curr[t][t] = 0;
    
    /*std::cout << curr[0][0] << " " << curr[1][0] << " " << curr[2][0] << std::endl;
    std::cout << curr[0][1] << " " << curr[1][1] << " " << curr[2][1] << std::endl;
    std::cout << curr[0][2] << " " << curr[1][2] << " " << curr[2][2] << std::endl;*/
    
    int r = 0;
    for(int t1 = 0; t1 < 3; t1++) {
        for(int t2 = 0; t2 < 3; t2++) {
            if(t1 != t2) {
                int m = std::min(curr[t1][t2], curr[t2][t1]);
                r += m;
                curr[t1][t2] -= m;
                curr[t2][t1] -= m;
            }
        }
    }
    
    for(int t1 = 0; t1 < 3; t1++) {
        for(int t2 = 0; t2 < 3; t2++) {
            for(int t3 = 0; t3 < 3; t3++) {
                if(t1 != t2 && t2 != t3 && t1 != t3) {
                    int m = std::min(curr[t1][t2], std::min(curr[t2][t3], curr[t3][t1]));
                    r += 2 * m;
                    curr[t1][t2] -= m;
                    curr[t2][t3] -= m;
                    curr[t3][t1] -= m;
                }
            }
        }
    }
    
    for(int t1 = 0; t1 < 3; t1++) {
        for(int t2 = 0; t2 < 3; t2++) {
            if(curr[t1][t2] != 0)
                return -1;
        }
    }
    
	return r;
}

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