Submission #1247866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247866		denislav	Combo (IOI18_combo)	C++20	100 / 100	7 ms	484 KiB

combo

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
# include "combo.h"
//# include "grader.cpp"

string guess_sequence(int N)
{
    vector<char> letters={'A','B','X','Y'};
    string s;
    int l=0,r=letters.size()-1,lett=0;
    while(l<r)
    {
        int mid=(l+r)/2;
        string guess;
        for(int i=l;i<=mid;i++) guess.push_back(letters[i]);
        if(press(guess))
        {
            r=mid;
            lett=mid;
        }
        else
        {
            l=mid+1;
            lett=mid+1;
        }
    }
    s.push_back(letters[lett]);
    letters.erase(letters.begin()+lett);
    if(N==1) return s;

    //cout<<"->"<<s<<endl;

   for(int i=2;i<N;i++)
   {
       string guess=s+letters[0]+s+letters[1]+letters[0]+s+letters[1]+letters[1]+s+letters[1]+letters[2];
       int resp=press(guess);
       if(resp==i) s.push_back(letters[0]);
       else if(resp==i+1) s.push_back(letters[1]);
       else s.push_back(letters[2]);
   }

   string guess=s+letters[0];
   if(press(guess)==N) s.push_back(letters[0]);
   else
   {
       guess=s+letters[1];
       if(press(guess)==N) s.push_back(letters[1]);
       else s.push_back(letters[2]);
   }

   return s;
}

/*
ABXYY
*/

/*
YXX
*/

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