Submission #589018

#	Time	Username	Problem	Language	Result	Execution time	Memory
589018		Mahtimursu	Combo (IOI18_combo)	C++17	97 / 100	47 ms	628 KiB

combo

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

using namespace std;

string opt[] = {"A", "B", "X", "Y"};
vector<string> oth; 

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();


string find_first() {
    string p = "";
    int tre = 0;
    bool ok = 0;
    for (string c : opt) {
        if (p.length() > 0 && c == string(1, p[0])) continue;

        if (ok || press(p + c) == (int)p.length() + 1) {
            p += c;
            break;
        } else tre++;

        if (p.length() > 0 && tre == 2) ok = 1;
        if (p.length() == 0 && tre == 3) ok = 1;
    }

    for (string c : opt) {
        if (string(1, p[0]) != c) oth.push_back(c);
    }

    return p;
}

string find_two(string sd) {
    shuffle(oth.begin(), oth.end(), mt19937(seed));
    vector<string> cmb;

    for (int i = 0; i < 2; ++i) {
        cmb.push_back(oth[0] + oth[i]);
    }
    cmb.push_back(oth[1] + oth[0]);

    string q;
    for (auto x : cmb) q += sd + x;

    int out = press(q) - sd.length();

    if (out == 2) {
        out = press(sd + oth[0] + oth[1]) - sd.length();
        if (out == 2) return oth[0] + oth[1];
        if (out == 1) return oth[0] + oth[0];
        if (out == 0) return oth[1] + oth[0];
    } else if (out == 1) {
        out = press(sd + oth[1] + oth[1]) - sd.length();

        if (out == 2) return oth[1] + oth[1];
        if (out == 1) return oth[1] + oth[2];
        if (out == 0) return oth[0] + oth[2];
    } else {
        return oth[2];
    }
} 

string find_one(string p) {
    int tre = 0;
    bool ok = 0;
    for (string c : opt) {
        if (p.length() > 0 && c == string(1, p[0])) continue;

        if (ok || press(p + c) == (int)p.length() + 1) {
            p += c;
            break;
        } else tre++;

        if (p.length() > 0 && tre == 2) ok = 1;
        if (p.length() == 0 && tre == 3) ok = 1;
    }

    return p;
}

string guess_sequence(int N) {
    oth.clear();
    string p = find_first();

    while ((int)p.length() + 2 <= N) {
        p += find_two(p);
    }
    if ((int)p.length() != N) {
        p = find_one(p);
    }

    return p;
}


/*

S'AA S'AB S'BA

2 -> AA/AB/BA
-> Kysy AB
    -> 2 = AB
    -> 1 = AA
    -> 0 = BA
1 -> AX/BB/BX
-> Kysy BB
    -> 2 = BB
    -> 1 = BX
    -> 0 = AX
0 -> XA/XB/XX
    -> Lisää X

*/

Compilation message (stderr)

combo.cpp: In function 'std::string find_two(std::string)':
combo.cpp:37:20: warning: control reaches end of non-void function [-Wreturn-type]
   37 |     vector<string> cmb;
      |                    ^~~

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