제출 #734684

#제출 시각아이디문제언어결과실행 시간메모리
734684rainliofficial콤보 (IOI18_combo)C++14
5 / 100
1 ms236 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; int n; vector<char> c = {'A', 'B', 'X', 'Y'}, cc; 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"; } 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); } } 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; } // int main(){ // // cin.tie(0); ios_base::sync_with_stdio(0); // // freopen("file.in", "r", stdin); // // freopen("file.out", "w", stdout); // int T = 100; // while (T--){ // N = 20; // S = 'A'; // for (int i=1; i<N; i++) { // char nx; // while ((nx = c[uid(0, 3)]) == S[0]) { // } // S += nx; // } // assert(sz(S) == N); // num_moves = 0; // std::string answer = guess_sequence(N); // if (answer != S) { // cout << S << " " << answer << "\n"; // wrong_answer("wrong guess"); // exit(0); // } // printf("Accepted: %d\n", num_moves); // } // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...