Submission #1276772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276772		abyfu	Combo (IOI18_combo)	C++20	10 / 100	9 ms	468 KiB

combo

#include <bits/stdc++.h>
#include "combo.h"
using namespace std;
#define pb push_back
#define ll long long
vector<string> rt;
int nn;
vector<char> mx = {'A', 'B', 'X', 'Y'};

void bt(string r, int u){
    if (u == nn){
        rt.pb(r);
    }
    else {
        for (int i = 0; i < 4; i++){
            bt(r + mx[i], u + 1);
        }
    }
}



string guess_sequence(int n){
    nn = n;
    if (n == 3){
        bt("", 0);
        for (auto i : rt){
            if (press(i) == n){
                return i;
            }
        }
    }
    else {
        string res = "";
        int flim = -1, lst = -1;
        string a[4];
        a[0] = "A"; a[1] = "B"; a[2] = "X"; a[3] = "Y";
        for (int i = 1; i <= n; i++){
            for (int j = 0; j < 4; j++){
                a[j] += a[j][0];
            }
        }
        int coins = 0;
        while (1){
            if (press(res) == n) return res;
            else {
                for (int i = 0; i < 4; i++){
                    if (i != flim && i != lst){
                        int u = press(res + a[i]);
                        if (u > coins){
                            res += a[i].substr(0, u - coins);
                            if (res == a[i].substr(0, u - coins)){
                                flim = i;
                            }
                            lst = i;
                            coins = u;
                        }
                    }
                }
            }
        }
    }
}

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

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