제출 #444399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444399		xiaowuc1	콤보 (IOI18_combo)	C++17	100 / 100	36 ms	612 KiB

combo

#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();
}
*/

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