Submission #1305924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305924		fafnir	Combo (IOI18_combo)	C++20	5 / 100	2 ms	400 KiB

combo

// #define LOCAL 1

#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 ABC[] = "ABXY";
char REM[3];


string guess_sequence(int N) {
    string s;

    if (press("AB")) {
        if (press("A")) {s += "A";}
        else {s += "B";}
    } else {
        if (press("X")) {s += "X";}
        else {s += "Y";}
    }

    {
        int idx = 0;
        REP(i, M) {
            if (s[0] != ABC[i]) {REM[idx++] = ABC[i];}
        }
    }

    REP(i, N-2) {
        string ns = s + REM[0] + REM[0] +
                    s + REM[0] + REM[1] +
                    s + REM[0] + REM[2] + s + REM[1];


        int q = press(ns);
        
        if (q == i+3) {s += REM[0];}
        else if (q == i+2) {s += REM[1];}
        else {s += REM[2];}
        
    }

    REP(j, M-2) {
        if (press(s + REM[j]) == N) {s += REM[j]; break;}
    }

    if (s.length() < N) {s += REM[M-2];}
    
    return s;
}

#ifdef LOCAL

string SECRET = "AXYXYXBXYXXYXY";
int calls = 0;

int press(string p) {
    calls++;
    assert(p.length() <= SECRET.length() * 4);
    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';    
    assert(calls <= (SECRET.length() + 2));
}

#endif

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