제출 #734688

#제출 시각아이디문제언어결과실행 시간메모리
734688rainliofficial콤보 (IOI18_combo)C++11
5 / 100
1 ms464 KiB
#include "combo.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define uid(a, b) uniform_int_distribution<int>(a, b)(rng) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /* Date: 2023/05/02 11:56 Problem Link: Topic(s): Reflection: Solution Notes: We can obtain the first character in 2 moves: guess AB if (>=1): then A or B else: then X or Y Then we want to be able to determine 3 characters for every 1 query. Notice we get 4N queries, so it has something to do with 4 possibilities with every query. I initally didn't utilize the 4N constraint, and I thought about queries 2 new characters every time. If we have X, we query XAB: I hoped this would amortize to N queries. However, this would still end up with the issue of having to determine > 2 possibilities with 1 query. Another key constraint is that the first character in S cannot appear again. We can thus use the first character, (e.g. X), to split differrent strings that we want to query. Consider the following method: X___ X___ X___ X___ What can we put in each of the empty spaces to for sure know the next character? XA XBA XBB XBC If A is the next character -> return 1 If B is next char -> return 2 If Y is next character -> 0 */ const int MAXN = 2e5+5, INF = 1e9; vector<char> c = {'A', 'B', 'X', 'Y'}; string guess_sequence(int n){ string s; int x = press(s + "AB"); if (x > 0){ // start with A if (press(s + 'A') > 0) s += 'A'; else s += "B"; }else{ if (press(s + 'X') > 0) s += "X"; else s += "Y"; } vector<char> cc; for (char j : c) if (j != s[0]) cc.push_back(j); for (int i=1; i<n-1; i++){ string q; q += s + cc[0]; for (int j=0; j<3; j++){ q += s + cc[1] + cc[j]; } x = press(q); if (x == sz(s)) s += cc[2]; else if (x == sz(s) + 1) s += cc[0]; else if (x == sz(s) + 2) s += cc[1]; else{ assert(false); } } assert(sz(s) == n-1); if (press(s + cc[0]) > sz(s)) s += cc[0]; else if (press(s + cc[1]) > sz(s)) s += cc[1]; else s += cc[2]; return s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...