Submission #437160

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
437160	2021-06-26T00:43:57 Z	arwaeystoamneg	Mutating DNA (IOI21_dna)	C++17	100 / 100	61 ms	7332 KB

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 998244353;//    1000000007

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
#ifndef arwaeystoamneg
#include<dna.h>
#endif
const int MAX = 111111;
int prefix[MAX][3], prefix1[MAX][3][3], temp[3][3];
int n;
map<char, int>key = { {'A',0},{'C',1},{'T',2} };
void init(std::string a, std::string b)
{
	n = sz(a);
	F0R(i, n)
	{
		F0R(j, 3)prefix[i + 1][j] = prefix[i][j];
		prefix[i + 1][key[a[i]]]++;
		prefix[i + 1][key[b[i]]]--;
		F0R(j, 3)F0R(k, 3)prefix1[i + 1][j][k] = prefix1[i][j][k];
		prefix1[i + 1][key[a[i]]][key[b[i]]]++;
	}
}

int get_distance(int l, int r) 
{
	F0R(i, 3)if (prefix[r + 1][i] != prefix[l][i])return -1;
	F0R(i, 3)F0R(j, 3)temp[i][j] = prefix1[r + 1][i][j] - prefix1[l][i][j];
	int ans = 0;
	F0R(i, 3)temp[i][i] = 0;
	F0R(i, 3)
	{
		F0R(j, 3)
		{
			int x = min(temp[i][j], temp[j][i]);
			ans += x;
			temp[i][j] -= x;
			temp[j][i] -= x;
		}
	}
	ans += 2 * (*max_element(temp[0], temp[0] + 3));
	return ans;
}
#ifdef arwaeystoamneg
int main()
{
	setIO("test1");
	int n, q;
	assert(scanf("%d %d", &n, &q) == 2);
	char A[MAX + 1], B[MAX + 1];
	assert(scanf("%s", A) == 1);
	assert(scanf("%s", B) == 1);
	std::string a = std::string(A);
	std::string b = std::string(B);
	std::vector<int> x(q), y(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);
	std::vector<int> results(q);
	init(a, b);
	for (int i = 0; i < q; i++) {
		results[i] = get_distance(x[i], y[i]);
	}
	for (int i = 0; i < q; i++) {
		printf("%d\n", results[i]);
	}
	fclose(stdout);
	return 0;
}
#endif

Subtask #1
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	6728 KB	Output is correct
2	Correct	47 ms	6772 KB	Output is correct
3	Correct	46 ms	6364 KB	Output is correct
4	Correct	47 ms	6784 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	8 ms	5452 KB	Output is correct
5	Correct	8 ms	5464 KB	Output is correct
6	Correct	7 ms	5452 KB	Output is correct
7	Correct	8 ms	5196 KB	Output is correct
8	Correct	8 ms	5580 KB	Output is correct
9	Correct	6 ms	5580 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	8 ms	5452 KB	Output is correct
5	Correct	8 ms	5464 KB	Output is correct
6	Correct	7 ms	5452 KB	Output is correct
7	Correct	8 ms	5196 KB	Output is correct
8	Correct	8 ms	5580 KB	Output is correct
9	Correct	6 ms	5580 KB	Output is correct
10	Correct	46 ms	6788 KB	Output is correct
11	Correct	47 ms	6784 KB	Output is correct
12	Correct	46 ms	6760 KB	Output is correct
13	Correct	61 ms	6904 KB	Output is correct
14	Correct	47 ms	7168 KB	Output is correct
15	Correct	46 ms	7172 KB	Output is correct
16	Correct	43 ms	6760 KB	Output is correct
17	Correct	44 ms	6904 KB	Output is correct
18	Correct	46 ms	7148 KB	Output is correct
19	Correct	41 ms	6892 KB	Output is correct
20	Correct	41 ms	7028 KB	Output is correct
21	Correct	41 ms	7168 KB	Output is correct

Subtask #4
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	8 ms	5452 KB	Output is correct
5	Correct	8 ms	5464 KB	Output is correct
6	Correct	7 ms	5452 KB	Output is correct
7	Correct	8 ms	5196 KB	Output is correct
8	Correct	8 ms	5580 KB	Output is correct
9	Correct	6 ms	5580 KB	Output is correct
10	Correct	7 ms	5052 KB	Output is correct
11	Correct	8 ms	5580 KB	Output is correct
12	Correct	9 ms	5196 KB	Output is correct
13	Correct	8 ms	5452 KB	Output is correct
14	Correct	9 ms	5580 KB	Output is correct
15	Correct	7 ms	5580 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	6728 KB	Output is correct
2	Correct	47 ms	6772 KB	Output is correct
3	Correct	46 ms	6364 KB	Output is correct
4	Correct	47 ms	6784 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	8 ms	5452 KB	Output is correct
12	Correct	8 ms	5464 KB	Output is correct
13	Correct	7 ms	5452 KB	Output is correct
14	Correct	8 ms	5196 KB	Output is correct
15	Correct	8 ms	5580 KB	Output is correct
16	Correct	6 ms	5580 KB	Output is correct
17	Correct	46 ms	6788 KB	Output is correct
18	Correct	47 ms	6784 KB	Output is correct
19	Correct	46 ms	6760 KB	Output is correct
20	Correct	61 ms	6904 KB	Output is correct
21	Correct	47 ms	7168 KB	Output is correct
22	Correct	46 ms	7172 KB	Output is correct
23	Correct	43 ms	6760 KB	Output is correct
24	Correct	44 ms	6904 KB	Output is correct
25	Correct	46 ms	7148 KB	Output is correct
26	Correct	41 ms	6892 KB	Output is correct
27	Correct	41 ms	7028 KB	Output is correct
28	Correct	41 ms	7168 KB	Output is correct
29	Correct	7 ms	5052 KB	Output is correct
30	Correct	8 ms	5580 KB	Output is correct
31	Correct	9 ms	5196 KB	Output is correct
32	Correct	8 ms	5452 KB	Output is correct
33	Correct	9 ms	5580 KB	Output is correct
34	Correct	7 ms	5580 KB	Output is correct
35	Correct	1 ms	204 KB	Output is correct
36	Correct	49 ms	6372 KB	Output is correct
37	Correct	46 ms	6784 KB	Output is correct
38	Correct	47 ms	6908 KB	Output is correct
39	Correct	48 ms	7168 KB	Output is correct
40	Correct	54 ms	7212 KB	Output is correct
41	Correct	7 ms	5580 KB	Output is correct
42	Correct	43 ms	6924 KB	Output is correct
43	Correct	45 ms	7332 KB	Output is correct
44	Correct	43 ms	7172 KB	Output is correct
45	Correct	42 ms	6900 KB	Output is correct
46	Correct	41 ms	7208 KB	Output is correct
47	Correct	41 ms	7168 KB	Output is correct

Submission #437160

Compilation message

Subtask #1 21.0 / 21.0

Subtask #2 22.0 / 22.0

Subtask #3 13.0 / 13.0

Subtask #4 28.0 / 28.0

Subtask #5 16.0 / 16.0

Subtask #1
21.0 / 21.0

Subtask #2
22.0 / 22.0

Subtask #3
13.0 / 13.0

Subtask #4
28.0 / 28.0

Subtask #5
16.0 / 16.0