Advertisement
erek1e

IOI '18 - Combo

Jul 23rd, 2022
866
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include "combo.h"
  2.  
  3. using namespace std;
  4.  
  5. string ch = "ABXY";
  6.  
  7. string guess_sequence(int N) {
  8.   // Use 2 queries to find first character
  9.   string p = "";
  10.   for (int i = 0; i < 2*N; ++i) p += ch.substr(0, 2);
  11.   int c1, c2;
  12.   if (press(p)) c1 = 0, c2 = 1;
  13.   else c1 = 2, c2 = 3;
  14.  
  15.   p = string(4*N, ch[c1]);
  16.   if (!press(p)) swap(c1, c2);
  17.   if (c1 != 0) swap(ch[0], ch[c1]);
  18.  
  19.   string S(1, ch[0]); // build the answer in this string
  20.  
  21.   // Use 1 query each for all remaining characters except last one
  22.   for (int i = 1; i < N-1; ++i) {
  23.     p = S + ch[2];
  24.     for (int j = 1; j <= 3; ++j) p += S + ch[3] + ch[j];
  25.     while ((int)p.size() < 4*N) p.push_back(ch[0]);
  26.  
  27.     int coins = press(p);
  28.     if (coins == i) S.push_back(ch[1]);
  29.     else if (coins == i+1) S.push_back(ch[2]);
  30.     else S.push_back(ch[3]); // coins == i+2
  31.   }
  32.  
  33.   // Use final 2 queries to find last character
  34.   if (N > 1) {
  35.     p = S + ch[1];
  36.     while ((int)p.size() < 4*N) p.push_back(ch[0]);
  37.     if (press(p) == N) S.push_back(ch[1]);
  38.     else {
  39.       p[N-1] = ch[2];
  40.       if (press(p) == N) S.push_back(ch[2]);
  41.       else S.push_back(ch[3]);
  42.     }
  43.   }
  44.   return S;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement