Submission #588976

#	Time	Username	Problem	Language	Result	Execution time	Memory
588976		Mahtimursu	Combo (IOI18_combo)	C++17	30 / 100	47 ms	604 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 (string c : oth) {
        cmb.push_back(oth[0] + c);
    }
    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) {
        q.clear();
        q = sd + cmb[0] + sd + cmb[1];

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

        if (out == 2) {
            out = press(sd + cmb[0]) - sd.length();

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

        if (out == 2) return oth[1] + oth[1];
        else return oth[1] + oth[2];
    } else {
        return oth[2];
        vector<string> opt;
        for (int i = 0; i < 3; ++i) opt.push_back(oth[2] + oth[i]);

        for (int i = 0; i < 2; ++i) {
            if (press(sd + opt[i]) == (int)sd.length() + 2) return opt[i];
        }
        return opt[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'AX S'BA

2 -> Jokin näistä
-> 2/1 kyselyä vielä = 3/2
1 -> Alkaa B, mutta ei ole BA
-> 1 kysely vielä = 2
0 -> Ei ala B, eikä ole A_
-> 0 enää kyselyä ja saadaan 1 merkki

S'AA S'AB S'BA S'BB

2 -> Jokin näistä
-> Kysy S'

*/

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