Submission #270830

#	Time	Username	Problem	Language	Result	Execution time	Memory
270830		cjoa	Combo (IOI18_combo)	C++11	100 / 100	39 ms	584 KiB

combo

#include "combo.h"

#include <iostream>

using namespace std;

const string letters = "ABXY";

std::string guess_sequence(int N) {
// cerr << "N:" << N << endl;
   string res;

   // determine first letter
   char matched_first_char;
   string cand = letters.substr(0, 2);
   int coins = press(cand);
   if (coins == 2) {
      res += cand;
      matched_first_char = cand[0];
   }
   else {
      if (coins == 0)
         cand = letters.substr(2);
      coins = press(cand.substr(0, 1));
      matched_first_char = cand[ coins == 0 ? 1 : 0 ];
      res += matched_first_char;
   }
   cand = letters;
   int p = cand.find(matched_first_char);
   swap(cand[p], cand[3]);
// cerr << "cand: " << cand << endl;

   // determine letters upto N-1
   for (int n = res.size(); n < N-1; ++n) {
      string guess = res;
      guess += cand[1];
      for (int k = 0; k < 3; ++k) {
         guess += res;
         guess += cand[2];
         guess += cand[k];
      }
      coins = press(guess);
      int k = coins - res.size();
   // cerr << "n:" << n << "  guess:" << guess << "  coins:" << coins << endl;
      res += cand[k];
   // cerr << "res:" << res << endl;
   }

   // determine last letter
   if (int(res.size()) < N) {
      string guess = res;
      guess += cand[0];
      guess += cand[3];
      guess += res;
      guess += cand[1];
      coins = press(guess);
      if (coins == N) {
         guess = res + cand[0];
         coins = press(guess);
         if (coins == N)
            res += cand[0];
         else
            res += cand[1];
      }
      else
         res += cand[2];
   }

// cerr << "res: " << res << endl;
   
   return res;
}

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