Submission #991088

#	Time	Username	Problem	Language	Result	Execution time	Memory
991088		fv3	Combo (IOI18_combo)	C++14	100 / 100	20 ms	2036 KiB

combo

#include <bits/stdc++.h>
#include "combo.h"

using namespace std;
typedef long long ll;

string guess_sequence(int N)
{
    char first;
    string sequence = "";

    if (press("AB"))
        first = (press("A") ? 'A' : 'B');
    else
        first = (press("X") ? 'X' : 'Y');
    
    sequence += first;
    // q = 2

    if (N == 1)
        return sequence;

    char c[3] = {'A', 'B', 'X'};
    if (first == 'A') c[0] = 'Y';
    else if (first == 'B') c[1] = 'Y';
    else if (first == 'X') c[2] = 'Y';

    for (int i = 1; i < N - 1; i++)
    {
        string s = sequence + c[0] + c[0] + sequence + c[0] + c[1] + sequence + c[0] + c[2] + sequence + c[1];
        int n = press(s);
        if (n == (int)sequence.size()) sequence += c[2];
        else if (n == (int)sequence.size() + 1) sequence += c[1];
        else sequence += c[0];
    }
    // q = N 
    
    if (press(sequence + c[0] + sequence + c[1]) == N)
        sequence += (press(sequence + c[0]) == N ? c[0] : c[1]);
    else
        sequence += c[2];

    return sequence;

}

// Let A be the first letter
// Guess the following:
// AXB AXX AXY AY
// N = 3 -> X
// N = 2 -> Y
// N = 1 -> B
//
// Using this strategy I can find all letters in sequence up to N - 1 in N guesses:
// I can find the last value in 2 guesses
//
// Why doesn't it go through?
// It passes all my test cases

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