Submission #713064

#	Time	Username	Problem	Language	Result	Execution time	Memory
713064		tht2005	Combo (IOI18_combo)	C++17	30 / 100	98 ms	608 KiB

combo

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

using namespace std;

string tmp[100];

int solve(int l, int r) {
    if(l == r) {
        return l;
    }
    int m = (l + r) >> 1;
    string combo;
    for(int i = m + 1; i <= r; ++i) {
        for(char ch : tmp[i]) {
            combo.push_back(ch);
        }
    }
    if(press(combo) >= (int)tmp[0].size()) {
        return solve(m + 1, r);
    }
    return solve(l, m);
}

string guess_sequence(int N) {
    string BUTTONS = "ABXY";
    for(int i = 0; i < 4; ++i) {
        tmp[i] = BUTTONS[i];
    }
    int first_button = solve(0, 3);
    swap(BUTTONS[3], BUTTONS[first_button]);
    string res(1, BUTTONS[3]);
    for(int i = 2; i <= N; i += 2) {
        if(i == N) {
            for(int j = 0; j < 3; ++j) {
                tmp[j] = res;
                tmp[j].push_back(BUTTONS[j]);
            }
            res.push_back(BUTTONS[solve(0, 2)]);
        }
        else {
            for(int j = 0; j < 3; ++j) {
                for(int k = 0; k < 3; ++k) {
                    tmp[3 * j + k] = res;
                    tmp[3 * j + k].push_back(BUTTONS[j]);
                    tmp[3 * j + k].push_back(BUTTONS[k]);
                }
            }
            int val = solve(0, 8);
            res.push_back(BUTTONS[val / 3]);
            res.push_back(BUTTONS[val % 3]);
        }
    }
    return res;
}

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