Submission #679303

#	Time	Username	Problem	Language	Result	Execution time	Memory
679303		That_Salamander	Combo (IOI18_combo)	C++14	100 / 100	26 ms	608 KiB

combo

#include <bits/stdc++.h>

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <string>

using namespace std;

int press(std::string p);

char CHARS[4] = {'A', 'B', 'X', 'Y'};

std::string guess_sequence(int N) {
    // Get first char
    int first;
    if (press("AB")) {
        if (press("A")) {
            first = 0;
        } else {
            first = 1;
        }
    } else if (press("X")) {
        first = 2;
    } else {
        first = 3;
    }

    string res = " ";
    res[0] = CHARS[first];

    vector<char> cs;
    for (char c : CHARS) {
        if (c != CHARS[first]) cs.push_back(c);
    }

    while (res.size() < N){
        if (res.size() == N - 1) {
            if (press(res + cs[0] + res + cs[1]) == res.size() + 1) {
                if (press(res + cs[0]) == res.size() + 1) {
                    res += cs[0];
                } else {
                    res += cs[1];
                }
            } else {
                res += cs[2];
            }
        } else {
            #define A cs[0]
            #define B cs[1]
            #define C cs[2]
            int x = press(res + A + A + res + A + B + res + B + A) - res.size();
            if (x == 2) {
                int y = press(res + A + A) - res.size();
                if (y == 0) {
                    res = res + B + A;
                } else if (y == 1) {
                    res = res + A + B;
                } else {
                    res = res +A + A;
                }
            } else if (x == 1) {
                int y = press(res + B + B) - res.size();
                if (y == 0) {
                    res = res + A + C;
                } else if (y == 1) {
                    res = res + B + C;
                } else if (y == 2) {
                    res = res + B + B;
                }
            } else {
                res = res + C;
            }
            #undef A
            #undef B
            #undef C
        }
    }

    return res;
}

#ifdef LOCAL_TEST
#include <random>
namespace {

constexpr int MAX_N = 2000;
constexpr int MAX_NUM_MOVES = 8000;

int N;
std::string S;

int num_moves;

void wrong_answer(const char *MSG) {
    printf("Wrong Answer: %s\n", MSG);
    exit(0);
}

}  // namespace

int press(std::string p) {
    if (++num_moves > MAX_NUM_MOVES) {
        wrong_answer("too many moves");
    }
    int len = p.length();
    if (len > 4 * N) {
        wrong_answer("invalid press");
    }
    for (int i = 0; i < len; ++i) {
        if (p[i] != 'A' && p[i] != 'B' && p[i] != 'X' && p[i] != 'Y') {
            wrong_answer("invalid press");
        }
    }
    //cout << "Testing " << p << endl;
    int coins = 0;
    for (int i = 0, j = 0; i < len; ++i) {
        if (j < N && S[j] == p[i]) {
            ++j;
        } else if (S[0] == p[i]) {
            j = 1;
        } else {
            j = 0;
        }
        coins = std::max(coins, j);
    }
    //cout << "Res = " << coins << endl;
    return coins;
}

int main() {
    /*char buffer[MAX_N + 1];
    if (scanf("%s", buffer) != 1) {
      fprintf(stderr, "Error while reading input\n");
      exit(1);
    }
    S = buffer;
    N = S.length();*/

    bool full = true;
    for (int i = 0; i < 10000; i++) {
        N = rand() % 50 + 1;

        S.resize(N);

        for (int i = 0; i < N; i++) {
            char c;
            do {
                c = CHARS[rand() % 4];
            } while (i != 0 && S[0] == c);
            S[i] = c;
        }

        cout << S << endl;

        num_moves = 0;
        std::string answer = guess_sequence(N);
        if (answer != S) {
            cout << "Guess:\n"
                 << answer << endl;
            wrong_answer("wrong guess");
            exit(0);
        }
        if (num_moves > N + 2) {
            cout << ":(" << endl;
            full = false;
        }
        printf("Accepted: %d\n", num_moves);
    }
    if (full) cout << "Full solution! :D" << endl;
    return 0;
}
#endif

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:37:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |     while (res.size() < N){
      |            ~~~~~~~~~~~^~~
combo.cpp:38:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         if (res.size() == N - 1) {
      |             ~~~~~~~~~~~^~~~~~~~
combo.cpp:39:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if (press(res + cs[0] + res + cs[1]) == res.size() + 1) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
combo.cpp:40:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                 if (press(res + cs[0]) == res.size() + 1) {
      |                     ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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