Submission #528653

#	Time	Username	Problem	Language	Result	Execution time	Memory
528653		rayfish	Combo (IOI18_combo)	C++17	100 / 100	30 ms	628 KiB

combo

#include <climits>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <vector>

#include "combo.h"

using namespace std;
using ll = long long;

//int press(string s) {
//    return 0;
//}
string guess_sequence(int N) {
    string cur;
    string letters[] {"A", "B", "X", "Y"};
    // find first letter
    string first;
    if (press(letters[0] + letters[1]) > 0) {
        if (press(letters[0]) == 1) {
            first = letters[0];
        } else {
            first = letters[1];
        }
    } else {
        if (press(letters[2]) == 1) {
            first = letters[2];
        } else {
            first = letters[3];
        }
    }
    cur += first;
    if (N == 1)
        return cur;
    // array without first
    string n_letters[3]; int nxt = 0;
    for (string c : letters) {
        if (c != first)
            n_letters[nxt++] = c;
    }
    // find next letters
    for (int i = 1; i < N - 1; i++) {
        int p_len = press(cur + n_letters[0] + n_letters[0]
                          + cur + n_letters[0] + n_letters[1]
                          + cur + n_letters[0] + n_letters[2]
                          + cur + n_letters[1]);
        if (p_len == i)
            cur += n_letters[2];
        else if (p_len == i + 1)
            cur += n_letters[1];
        else
            cur += n_letters[0];
    }
    if (press(cur + n_letters[0]) == N) {
        cur += n_letters[0];
    } else if (press(cur + n_letters[1]) == N) {
        cur += n_letters[1];
    } else {
        cur += n_letters[2];
    }
    return cur;
}

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