Submission #1305911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305911		fafnir	Combo (IOI18_combo)	C++20	10 / 100	17 ms	444 KiB

combo

#include <bits/stdc++.h>
#ifndef LOCAL
#include "combo.h"
#endif
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)


#ifdef LOCAL
int press(string s);
#endif


const int M = 4;
char EXC = '\0';
char ABC[] = "ABXY";

string guess_sequence(int N) {
    string s;
    int len[M];

    // Guess first
    REP(j, M) {
        if ((j == M-1) || (press(s + ABC[j]) == 1)) {
            EXC = ABC[j];
            s += ABC[j];
            break;
        }
    }

    assert(EXC != '\0');

    REP(i, N-1) {
        // random_shuffle(ABC, ABC + M);
        REP(j, M) {
            if (ABC[j] == EXC) {continue;}
            if ((j == M-1) || (press(s + ABC[j]) == i+2)) {
                s += ABC[j];
                break;
            }
        }
    }
    
    return s;
}

#ifdef LOCAL

string SECRET = "ABBBXBXBXBYYYYBBY";

int press(string p) {
    const int m = p.length();
    const int n = SECRET.length();
    int lpref = 0;

    REP(i, m) {
    
        int j = 0;
        while (j < n && i+j < m && SECRET[j] == p[i+j]) {j++;}

        lpref = max(lpref, j);
    }

    return lpref;
}

int main() {
    cout << guess_sequence(SECRET.length()) << '\n';    
}

#endif

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