제출 #299783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299783		tzero	콤보 (IOI18_combo)	C++14	0 / 100	1 ms	328 KiB

combo

#include "combo.h"
#include <vector>
#include <algorithm>
using namespace std;

void dfs1(string & seq, string & s, int max_len, int n, vector<vector<bool> > & dp) {
  int len = (int)s.size(), sum = 0;
  for(int i = 0; i < 4; i++) sum += (dp[len][i] ? 1 : 0); 
  vector<char> chars = {'A', 'B', 'X', 'Y'};

  if((int)seq.size() + len > 4 * n) return;
  if(len == max_len) { seq += s; return; } 

  int checked = 0;
  for(int i = 0; i < 4 && checked < sum - 1; i++) if(dp[len][i]) { 
    s.push_back(chars[i]);
    dfs1(seq, s, max_len, n, dp);
    s.pop_back();
    checked++;
  } 
}

void dfs2(int & seq_len, int len, int max_len, int n, vector<vector<bool> > & dp, int coins) {
  bool right = len < coins, first_incorrect = len == coins; 
  int sum = 0;
  for(int i = 0; i < 4; i++) sum += (dp[len][i] ? 1 : 0);

  if(seq_len + len > 4 * n) return;
  if(len == max_len) { seq_len += len; return; } 

  if(right) {
    int checked = 0, i = 0; 
    for(; i < 4 && checked < sum - 1; i++) if(dp[len][i]) { 
      checked++;
    }
    for(; i < 4; i++) {
      // we were right here without using this one
      // so it must be false
      dp[len][i] = false;
    }
  } else if(first_incorrect) {
    int checked = 0, i = 0;
    for(; i < 4 && checked < sum - 1; i++) if(dp[len][i]) {
      dp[len][i] = false;
      checked++;
    }
  }

  // we simulate the search
  int checked = 0;
  for(int i = 0; i < 4 && checked < sum - 1; i++) if(dp[len][i]) { 
    dfs2(seq_len, len + 1, max_len, n, dp, coins);
    checked++;
  } 
}

char guess_next(string & s, int n, vector<vector<bool> > & dp) {
  int len = s.size(), sum = 0;
  for(int i = 0; i < 4; i++) sum += (dp[len][i] ? 1 : 0);
  vector<char> chars = {'A', 'B', 'X', 'Y'};

  int checked = 0;
  for(int i = 0; i < 4; i++) if(dp[len][i]) {
    char c = chars[i];
    if(checked == sum - 1) return c;
  
    int max_len = max(len + 20, n);
    string seq = "";
    string s = "";
    int seq_len = 0;

    dfs1(seq, s, max_len, n, dp);  

    while(seq.size() < 4 * n) seq += c;
    int coins = press(seq); 

    dfs2(seq_len, 0, max_len, n, dp, coins); 

    if(len == 0 && coins > 0) {
      for(int j = 1; j < n; j++) {
        dp[j][i] = false;
      }
    }

    if(coins > len) return chars[i];
  }
}

string guess_sequence(int n) {
  string s = "";
  vector<vector<bool> > dp(n, vector<bool>(4, true));

  for(int i = 0; i < n; i++) {
    s += guess_next(s, n, dp);
  }

  return s;
}

컴파일 시 표준 에러 (stderr) 메시지

combo.cpp: In function 'char guess_next(std::string&, int, std::vector<std::vector<bool> >&)':
combo.cpp:74:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     while(seq.size() < 4 * n) seq += c;
      |           ~~~~~~~~~~~^~~~~~~
combo.cpp:60:43: warning: control reaches end of non-void function [-Wreturn-type]
   60 |   vector<char> chars = {'A', 'B', 'X', 'Y'};
      |                                           ^

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