Submission #874386

#	Time	Username	Problem	Language	Result	Execution time	Memory
874386		mooshroom	Combo (IOI18_combo)	C++17	97 / 100	45 ms	11588 KiB

combo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#include "combo.h"
 
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define st first
#define nd second
#define vt vector
#define VAR(__var)  #__var << ": " << __var << " "
#define PAIR(__var) #__var << ": " << __var.first << ", " << __var.second << " "
#define FOR(__var, __start, __end)  for(int __var=__start; __var<__end; ++__var)
#define FORB(__var, __start, __end) for(int __var=__start; __var>__end; --__var)
#define REP(__var, __cnt) for(int __var=0; __var<(__cnt); ++__var)
#define EACH(__var, __x) for(auto __var : __x)
#define maxi(__x, __y) __x = (__x>__y?__x:__y)
#define mini(__x, __y) __x = (__x<__y?__x:__y)
#define all(__var)     (__var).begin(),(__var).end()
#define rall(__var)    (__var).rbegin(),(__var).rend()
#define sz(__var)      (int)(__var).size()

using namespace std;
 
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#ifdef DEBUG
template<typename Stream, typename T1, typename T2>
Stream& operator << (Stream& out, pair<T1, T2> a) {return out << "(" << a.st << ", " << a.nd << ")";}
 
template<typename Stream, typename T>
Stream &operator << (Stream& out, T v) {
	out << "{";
	int i = 0;
	for (auto x : v)
		out << x << ((++ i) != sz(v) ? ", " : "");
	return out << "}";
}
 
template<typename... Args>
void dump(Args... x) {((cerr << x << ", "), ...) << '\n';}
 
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif
 
typedef       long long ll;
typedef     long double ld;
typedef   pair<ll, ll> pll;
typedef pair<int, int> pii;

const bool __test_cases = false;
 
const int INF = 1e9+2137;

string guess_sequence(int N) {
	string now;

	mt19937 rng(213769);
	vt<string> ord = {"X", "A", "Y", "B"};
	shuffle(all(ord), rng);
	
	int tried = 0;
	for(auto c : ord) {
		if(tried == 3) {
			now = c;
			break;
		}
		int got = press(c);
		if(got == 1) {
			now = c;
			break;
		}
		++tried;
	}

	vt<string> tmp;
	for(auto x : ord)
		if(x != now)
			tmp.pb(x);
	swap(tmp, ord);
	
	int prev = 1;
	while(sz(now) < N) {
		shuffle(all(ord), rng);
		string q;
		for(auto c : ord)
			q += now + ord[0] + c;
		q += now + ord[1];
		if(sz(q) > 4*N) {
			int tried = 0;
			for(auto c : ord) {
				if(tried == 2) {
					now += c;
					++prev;
					break;
				}
				int got = press(now + c);
				++tried;
				if(got == prev+1) {
					now += c;
					++prev;
					break;
				}
			}
			continue;
		}
		int got = press(q);
		cerr << "now: " << now << '\n';
		cerr << "press: " << q << '\n';
		cerr << "got: " << got << '\n';
		if(got == prev)
			++prev, now += ord[2];
		else if(got == prev+1)
			++prev, now += ord[1];
		else
			++prev, now += ord[0];
	}
	return now;
}

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