Submission #588957

#	Time	Username	Problem	Language	Result	Execution time	Memory
588957		Mahtimursu	Combo (IOI18_combo)	C++17	30 / 100	58 ms	608 KiB

combo

#include "combo.h"
#include <vector>

using namespace std;

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

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) {
    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 {
        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]) == 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 (p.length() + 2 <= N) {
        p += find_two(p);
    }
    if (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?
-> 2 kyselyä vielä = 3

*/

Compilation message (stderr)

combo.cpp: In function 'std::string find_two(std::string)':
combo.cpp:69:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             if (press(sd + opt[i]) == sd.length() + 2) return opt[i];
      |                 ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:97:27: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |     while (p.length() + 2 <= N) {
      |            ~~~~~~~~~~~~~~~^~~~
combo.cpp:100:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     if (p.length() != N) {
      |         ~~~~~~~~~~~^~~~

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