Submission #694931

#	Time	Username	Problem	Language	Result	Execution time	Memory
694931		nasir_bashirov	Mutating DNA (IOI21_dna)	C++17	35 / 100	36 ms	7324 KiB

dna

#include "dna.h"
using namespace std;

int hsh[128], tbl[5][5][200005], cnt[5][200005], t[5][5];

void init(string a, string b){
    hsh['A'] = 1;
    hsh['C'] = 2;
    hsh['T'] = 3;
    a = ' ' + a;
    b = ' ' + b;
    for(int i = 1; i < a.size(); i++){
        cnt[hsh[a[i]]][i]++, cnt[hsh[b[i]]][i]--;
        for(int j = 1; j <= 3; j++){
            cnt[j][i] += cnt[j][i - 1];
        }
        for(int j = 1; j <= 3; j++){
            for(int k = 1; k <= 3; k++){
                tbl[j][k][i] = tbl[j][k][i - 1];
            }
        }
        tbl[hsh[a[i]]][hsh[b[i]]][i]++;
    }
}

int get_distance(int x, int y){
	x++, y++;
	for(int i = 1; i <= 3; i++){
		if(cnt[i][y] != cnt[i][x - 1]){
			return -1;
		}
	}
	for(int i = 1; i <= 3; i++){
		for(int j = 1; j <= 3; j++){
			t[i][j] = tbl[i][j][y] - tbl[i][j][x - 1];
		}
	}
	int res = 0, temp = min(t[1][2], t[2][1]);
	res += temp, t[1][2] - temp, t[2][1] - temp;
	temp = min(t[1][3], t[3][1]);
	res += temp, t[1][3] - temp, t[3][1] - temp;
	temp = min(t[2][3], t[3][2]);
	res += temp, t[2][3] - temp, t[3][2] - temp;
	return res + (max(t[1][2], t[2][1]) * 2);
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 1; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
dna.cpp:13:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   13 |         cnt[hsh[a[i]]][i]++, cnt[hsh[b[i]]][i]--;
      |                     ^
dna.cpp:13:42: warning: array subscript has type 'char' [-Wchar-subscripts]
   13 |         cnt[hsh[a[i]]][i]++, cnt[hsh[b[i]]][i]--;
      |                                          ^
dna.cpp:22:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |         tbl[hsh[a[i]]][hsh[b[i]]][i]++;
      |                     ^
dna.cpp:22:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |         tbl[hsh[a[i]]][hsh[b[i]]][i]++;
      |                                ^
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:39:23: warning: right operand of comma operator has no effect [-Wunused-value]
   39 |  res += temp, t[1][2] - temp, t[2][1] - temp;
      |               ~~~~~~~~^~~~~~
dna.cpp:39:39: warning: right operand of comma operator has no effect [-Wunused-value]
   39 |  res += temp, t[1][2] - temp, t[2][1] - temp;
      |                               ~~~~~~~~^~~~~~
dna.cpp:41:23: warning: right operand of comma operator has no effect [-Wunused-value]
   41 |  res += temp, t[1][3] - temp, t[3][1] - temp;
      |               ~~~~~~~~^~~~~~
dna.cpp:41:39: warning: right operand of comma operator has no effect [-Wunused-value]
   41 |  res += temp, t[1][3] - temp, t[3][1] - temp;
      |                               ~~~~~~~~^~~~~~
dna.cpp:43:23: warning: right operand of comma operator has no effect [-Wunused-value]
   43 |  res += temp, t[2][3] - temp, t[3][2] - temp;
      |               ~~~~~~~~^~~~~~
dna.cpp:43:39: warning: right operand of comma operator has no effect [-Wunused-value]
   43 |  res += temp, t[2][3] - temp, t[3][2] - temp;
      |                               ~~~~~~~~^~~~~~

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