제출 #613629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
613629		fvogel499	콤보 (IOI18_combo)	C++17	100 / 100	89 ms	832 KiB

combo

#include "combo.h"

#include <bits/stdc++.h>

#define sz(x) (int)((x).size())

using namespace std;

int finalQuery(string b) {
    for (int i = 0; i < sz(b); i++) {
        if (b[i] == 'C') {
            b[i] = 'X';
        }
        else if (b[i] == 'D') {
            b[i] = 'Y';
        }
    }
    return press(b);
}

int tripleQuery(vector<string> b, char firstChar) {
    string f = "";
    for (string& i : b) {
        for (int j = 0; j < sz(i); j++) {
            if (i[j] == firstChar) {
                i[j] = 'D';
            }
        }
        f += firstChar;
        f += i;
    }
    assert(!f.empty());
    return finalQuery(f);
}

string parse(string res) {
    for (int i = 0; i < sz(res); i++) {
        if (res[i] == 'C') res[i] = 'X';
        else if (res[i] == 'D') res[i] = 'Y';
    }
    return res;
}

string cts(char x) {
    string y = "";
    y += x;
    return y;
}

string guess_sequence(int n) {
    char firstChar;
    if (finalQuery("AB") >= 1) {
        if (finalQuery("A") >= 1) {
            firstChar = 'A';
        }
        else {
            firstChar = 'B';
        }
    }
    else {
        if (finalQuery("C") >= 1) {
            firstChar = 'C';
        }
        else {
            firstChar = 'D';
        }
    }
    if (n == 1) {
        return parse(cts(firstChar));
    }
    string cons = "";
    while (sz(cons)+2 < n) {
        int q = tripleQuery({cons+"AA", cons+"AB", cons+"AC", cons+"B"}, firstChar);
        if (q == sz(cons)+3) {
            cons += "A";
        }
        else if (q == sz(cons)+2) {
            cons += "B";
        }
        else {
            assert(q == sz(cons)+1);
            cons += "C";
        }
    }
    assert(sz(cons)+2 == n);
    while (sz(cons) < n-1) {
        if (tripleQuery({cons+"A"}, firstChar) == sz(cons)+2) {
            cons += "A";
        }
        else if (tripleQuery({cons+"B"}, firstChar) == sz(cons)+2) {
            cons += "B";
        }
        else {
            cons += "C";
        }
    }
    for (int i = 0; i < sz(cons); i++) if (cons[i] == firstChar) cons[i] = 'D';
    string res = cts(firstChar)+cons;
    return parse(res);
}

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