Submission #777875

#	Time	Username	Problem	Language	Result	Execution time	Memory
777875		JoenPoenMan	Combo (IOI18_combo)	C++17	30 / 100	47 ms	584 KiB

combo

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

using namespace std;

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

int findBestn(int N, int k) {
    int high = N-1, low = 1, mid;
    while (high != low) {
        mid = (high + low+1)/2;
        if ((mid+k)*pow(3, mid)/2 <= 4*N) low = mid;
        else high = mid - 1;
    } 
    return low;
}

vector<string> createStr(int n, char excl, string S = "") {
    if (n == 0) return {S};
    vector<string> res;
    for (char ch : chars) if (ch != excl) {
        vector<string> tmp = createStr(n-1, excl, S + ch);
        res.insert(res.end(), tmp.begin(), tmp.end()); 
    }
    return res;
}

string guess(int N, string S) {
    int n = min(findBestn(N, S.length()), (int)(N-S.length()));
    int i = (pow(3, n)+1)/2;
    vector<string> tmp = createStr(n, S[0]);
    
    vector<string> set1;
    vector<string> set2;
    while (tmp.size() > 1) {
        for (int i = 0; i < tmp.size(); i++) {
            if (i%2==1) set1.push_back(tmp[i]);
            else set2.push_back(tmp[i]);
        }
        string testStr = "";
        for (auto el : set1) {
            testStr += S + el;
        }
        int res = press(testStr);
        if (res == n+S.length()) tmp = set1;
        else tmp = set2;
        set1.clear();
        set2.clear();
    }  
    return tmp[0];
}

std::string guess_sequence(int N) {
    string S{};
    if (press("AB") >= 1) S = (press("A") ? "A" : "B");
    else S = (press("X") ? "X" : "Y");
    while (S.length() < N) S += guess(N, S);
    return S;
}

Compilation message (stderr)

combo.cpp: In function 'std::string guess(int, std::string)':
combo.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < tmp.size(); i++) {
      |                         ~~^~~~~~~~~~~~
combo.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (res == n+S.length()) tmp = set1;
      |             ~~~~^~~~~~~~~~~~~~~
combo.cpp:30:9: warning: unused variable 'i' [-Wunused-variable]
   30 |     int i = (pow(3, n)+1)/2;
      |         ^
combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:57:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     while (S.length() < N) S += guess(N, S);
      |            ~~~~~~~~~~~^~~

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