Submission #623923

#	Time	Username	Problem	Language	Result	Execution time	Memory
623923		ACGN	Mutating DNA (IOI21_dna)	C++17	100 / 100	64 ms	7464 KiB

dna

    #include<bits/stdc++.h>
    using namespace std;
     
    int cvt(char c) {
    	if (c=='A') return 0;
    	if (c=='C') return 1;
    	return 2;
    }
     
    int srg[3][3][150000];
    void init(string a, string b) {
    	int n=a.length();
    	for (int i=0;i<3;i++) {
    		for (int j=0;j<3;j++) {
    			srg[i][j][0] = 0;
    		}
    	}
     
    	for (int i=0;i<3;i++) {
    		for (int j=0;j<3;j++) {
    			for (int k=0;k<n;k++) srg[i][j][k+1] = srg[i][j][k] + (i==cvt(a[k]))*(j==cvt(b[k]));
    		}
    	}
    }
     
    int get_distance(int x, int y) {
    	int bs[3][3];
    	for (int i=0;i<3;i++) {
    		for (int j=0;j<3;j++) {
    			bs[i][j] = srg[i][j][y+1] - srg[i][j][x];
    		}
    	}
    	int ans = 0;
    	int m;
    	m=min(bs[0][1],bs[1][0]);bs[0][1]-=m;bs[1][0]-=m;ans+=m;
    	m=min(bs[0][2],bs[2][0]);bs[0][2]-=m;bs[2][0]-=m;ans+=m;
    	m=min(bs[2][1],bs[1][2]);bs[2][1]-=m;bs[1][2]-=m;ans+=m;
    	int r = bs[0][1];
    	if (r!=bs[1][2]) return -1;
    	if (r!=bs[2][0]) return -1;
    	ans+=r*2;
    	int s = bs[0][2];
    	if (s!=bs[2][1]) return -1;
    	if (s!=bs[1][0]) return -1;
    	ans+=s*2;
     
    	return ans;
    }

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