Submission #810802

#	Time	Username	Problem	Language	Result	Execution time	Memory
810802		TB_	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	11312 KiB

dna

#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

map<pair<char, char>, int> toIndex = {{{'A', 'A'}, 0}, {{'A', 'T'}, 1}, {{'A', 'C'}, 2}, {{'T', 'A'}, 3}, {{'T', 'T'}, 4}, {{'T', 'C'}, 5}, {{'C', 'A'}, 6}, {{'C', 'T'}, 7}, {{'C', 'C'}, 8}};
vvl prefSum;

void init(string a, string b) {
	prefSum.assign(9, vl(a.length()+1, 0));
	fo(i, a.length()){
		prefSum[toIndex[{a[i], b[i]}]][i+1] = 1;
	}
	fo(i, 9){
		fo(j, a.length()){
			prefSum[i][j+1] = prefSum[i][j+1]+prefSum[i][j];
		}
	}
}

int get_distance(int x, int y) {
	vl vals(9, 0);
	fo(i, 9) vals[i] = prefSum[i][y+1]-prefSum[i][x];
	ll ans = 0;

	vpl pos = {{1, 3}, {2, 6}, {5, 7}};
	fo(i, 3){
		ll temp = min(vals[pos[i].F], vals[pos[i].S]);
		ans+=temp;
		vals[pos[i].F] -= temp;
		vals[pos[i].S] -= temp;
	}

	vl pos2 = {1, 5, 6, 2, 3, 7};
	fo(i, 2){
		ll temp = min(vals[pos2[i*3]], min(vals[pos2[i*3+1]], vals[pos2[i*3+2]]));
		ans+=temp*2;
		vals[pos2[i*3]] -= temp;
		vals[pos2[i*3+1]] -= temp;
		vals[pos2[i*3+2]] -= temp;
	}
	fo(i, 6){
		if(vals[pos2[i]]) return -1;
	} 


	return ans;
}


// int main() {
// 	int n, q;
// 	assert(scanf("%d %d", &n, &q) == 2);
// 	char A[n+1], B[n+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;
// }

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