Submission #247435

#	Time	Username	Problem	Language	Result	Execution time	Memory
247435		srvlt	Combo (IOI18_combo)	C++14	100 / 100	42 ms	716 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

string guess_sequence(int N) {
	char c;
	if (press("AB") == 0) {
		if (press("X")) c = 'X';
		else c = 'Y';
	}	else {
		if (press("A")) c = 'A';
		else c = 'B'; 
	}
	//2
	vector <char> v;
	for (char i : "ABXY")
		if (i != c) v.pb(i);
	int cur = 1;
	string res = "", query;
	res.pb(c);
	while (cur < N - 1) {
		query = (res + v[0]) + (res + v[1] + v[0]) + (res + v[1] + v[1]) + (res + v[1] + v[2]);
		int coins = press(query);
		if (coins == cur) res += v[2];
		else {
			if (coins == cur + 1) res += v[0];
			else res += v[1];
		}
		cur++;
	}
	//n-2
	if (cur < N) {
		query = (res + v[0]) + (res + v[1]);
		int coins = press(query);
		if (coins == cur) res += v[2];
		else {
			query = (res + v[0]);
			if (press(query) == cur + 1) res += v[0];
			else res += v[1]; 
		}
	}
	//2
	return res;
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95