Submission #444399

#TimeUsernameProblemLanguageResultExecution timeMemory
444399xiaowuc1Combo (IOI18_combo)C++17
100 / 100
36 ms612 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <stack> #include <vector> #include "combo.h" using namespace std; // BEGIN NO SAD #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define eb emplace_back #define lb lower_bound #define ub upper_bound typedef vector<int> vi; #define f first #define s second // END NO SAD typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<vector<ll>> matrix; /* const string GOAL = "ABX"; int press(string s) { cerr << "PRESS: " << s << endl; string want = GOAL; while(sz(want)) { for(int i = 0; i + sz(want) <= sz(s); i++) if(s.substr(i, sz(want)) == want) return sz(want); want = want.substr(0, sz(want)-1); } return 0; } */ string guess_sequence(int n) { string alpha = "ABXY"; int v1 = press("AB"); int v2 = press("AX"); string prefix = ""; if(v1 > 0 && v2 > 0) { prefix = "A"; alpha.erase(alpha.begin() + 0); } else if(v1 > 0 && v2 == 0) { prefix = "B"; alpha.erase(alpha.begin() + 1); } else if(v1 == 0 && v2 > 0) { prefix = "X"; alpha.erase(alpha.begin() + 2); } else if(v1 == 0 && v2 == 0) { prefix = "Y"; alpha.erase(alpha.begin() + 3); } else assert(false); cerr << "alpha is " << alpha << endl; while(sz(prefix) < n-1) { string cand = prefix; cand += alpha[0]; cand += alpha[0]; cand += prefix; cand += alpha[0]; cand += alpha[1]; cand += prefix; cand += alpha[0]; cand += alpha[2]; cand += prefix; cand += alpha[1]; int pp = press(cand); if(pp == sz(prefix)+2) prefix += alpha[0]; else if(pp == sz(prefix)+1) prefix += alpha[1]; else if(pp == sz(prefix)+0) prefix += alpha[2]; else assert(false); } if(sz(prefix) == n) return prefix; string lhs = prefix; lhs += alpha[0]; lhs += prefix; lhs += alpha[1]; string rhs = prefix; rhs += alpha[0]; rhs += prefix; rhs += alpha[2]; v1 = press(lhs); v2 = press(rhs); if(v1 == n && v2 == n) return prefix + alpha[0]; if(v1 == n) return prefix + alpha[1]; if(v2 == n) return prefix + alpha[2]; assert(false); } /* void solve() { string ret = guess_sequence(sz(GOAL)); cerr << ret << endl; cerr << (ret == GOAL) << endl; } // what would chika do // are there edge cases (N=1?) // are array sizes proper (scaled by proper constant, for example 2* for koosaga tree) // integer overflow? // DS reset properly between test cases int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...