oj.uz

Submission #625318

# Submission time Handle Problem Language Result Execution time Memory
625318 2022-08-10T03:32:18 Z jole Mutating DNA (IOI21_dna) C++17
0 / 100
 29 ms 4236 KB 
#include <iostream>
#include <vector>

using namespace std;

struct Entry {
	int at, ac, tc;
};

vector<Entry> A;

void
init(string X, string Y) {
	int N = X.size();

	A.clear();
	A.reserve(N);

	for(int i = 0; i < N; ++i) {
		char x = X[i];
		char y = Y[i];

		int at = (x == 'A' && y == 'T') - (x == 'T' && y == 'A');
		int ac = (x == 'A' && y == 'C') - (x == 'C' && y == 'A');
		int tc = (x == 'T' && y == 'C') - (x == 'C' && y == 'T');

		if(i > 0) {
			Entry e = A[i-1];
			at += e.at;
			ac += e.ac;
			tc += e.tc;
		}
		A[i] = Entry {
			at, ac, tc
		};
	}
}

int
get_distance(int x, int y) {
	Entry a = A[x];
	Entry b = A[y];

	int at = b.at - a.at;
	int ac = b.ac - a.ac;
	int tc = b.tc - a.tc;

	// AT -> AT
	// TC -> CT

	// we can swap AT with TC to get AC

	int remaining = abs(at) + abs(ac) + abs(tc);
	int swaps = (y - x + 1) - remaining;

	if(at == tc) {
		int swapped = abs(at);
		ac += at;

		at = 0;
		tc = 0;
		// changes 
		if(ac != 0) {
			return -1;
		}

		swaps += swapped;
	}

	return swaps;
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 4236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 4236 KB Output isn't correct
2 Halted 0 ms 0 KB -