Submission #288549

#	Time	Username	Problem	Language	Result	Execution time	Memory
288549		dandrozavr	Combo (IOI18_combo)	C++14	94 / 100	65 ms	776 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC

vector < char > can = {'A', 'B', 'X', 'Y'};
int st = -1;

string fir(int len){
    string s;
    while(len--) s += can[0];
    return s;
}
string nxt(string s){
    int n = s.size();
    bool byl = 0;
    for (int i = n - 1; i >= 0; --i)
    if (s[i] != can.back()){
        int pos = 0;
        for (int j = 0; j < can.size(); ++j)
            if (can[j] == s[i]) pos = j;
        s[i] = can[pos + 1];        byl = 1;
        for (int j = i + 1; j < n; ++j)
            s[j] = can[0];
//        cout << s << endl;
        break;
    }
    if (!byl) return fir(n + 1);
    return s;
}
bool done;
#define psi pair < string, string >
string str[5005], STA;

psi check(int len, int mxlen, string& base){
    string ask;
    string s = fir(len);

    done = 1;
    int cur = 0;
    while(true){
        int add = 0;
        string ask1;
        if (ask.size() + 1 > mxlen) break;
        str[cur + 1 + base.size() + s.size() - 1] = s;
//        cout << cur _ s _ ask << endl;
        if (cur){
            string z = fir(cur);
            while(ask1.size() + ask.size() <= mxlen){
                if (z.size() == cur + 1) break;
                ask1 += base + s + z;
                z = nxt(z);
            }
        } else ask1 += base + s;
//        cout << s _ cur + 1 + base.size() + len - 1 _ mxlen _ ask.size() _ ask1.size() << endl;
        ++cur;
        if (ask1.size() + ask.size() > mxlen){
            done = 0;
//            cout << s << endl;
            return make_pair(ask, s);
        }
        ask += ask1;
//        vis.pb(s);
        s = nxt(s);
//        if (cur == 2) break;
    }
//    cout << str[4]<<endl;
    return make_pair(ask, s);
}
mt19937_64 gen(chrono::high_resolution_clock::now().time_since_epoch().count());


std::string guess_sequence(int N) {
    int n = N, kol = 0;
    string base;
    string now = "A";
//    if (n == 1){
    if (press("A") == 1) base = "A"; else
    if (press("B") == 1) base = "B"; else
    if (press("X") == 1) base = "X"; else
        base = "Y";
    STA = base;
    if (n == 1) return base;
    for (int i = 0; i < can.size(); ++i)
        if (can[i] == base.back()){
            can.erase(can.begin() + i);
            break;
        }
    while(base.size() + 1 != n){
        int ost = n - base.size();
        string ask;
        int l = 1;
        while(check(l, n * 4, base).S.size() > l) ++l;
        if (l == 1) break;
        --l;
        auto otv = check(l, 4 * n, base);
        int ans = press(otv.F);
//        cout << l << " " << otv.F _ otv.S _ ans << endl;
        base += str[ans];
        ++kol;
//        if (base.size() >= 3) break;
    }
//    cout << base _ kol << endl;
    while(base.size() != n){
        string ask = base + can[0];
        string dop;
        for (int i = 0; i < 3; ++i){
            dop += base + can[1] + can[i];
        }
//        cout << base _ ask _ dop << endl;
        if (ask.size() + dop.size() <= 4 * n || base.size() == n){
            ask += dop;
            int otv = press(ask);
//            cout << ask _ otv << endl;
            if (otv == base.size())
                base += can[2]; else
            if (otv == 1 + base.size())
                base += can[0]; else
                base += can[1];
        } else {
            shuffle(can.begin(), can.end(), gen);
            for (int i = 0; i < 3; ++i){
                string ask = base + can[i];
//                cout << base _ ask _ press(ask) << endl;
                if (press(ask) == base.size() + 1){
                    base += can[i];
                    break;
                }
            }
        }
//        break;
    }
    return base;
}

Compilation message (stderr)

combo.cpp: In function 'std::string nxt(std::string)':
combo.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int j = 0; j < can.size(); ++j)
      |                         ~~^~~~~~~~~~~~
combo.cpp: In function 'std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > check(int, int, std::string&)':
combo.cpp:53:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         if (ask.size() + 1 > mxlen) break;
      |             ~~~~~~~~~~~~~~~^~~~~~~
combo.cpp:58:44: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |             while(ask1.size() + ask.size() <= mxlen){
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
combo.cpp:59:30: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |                 if (z.size() == cur + 1) break;
      |                     ~~~~~~~~~^~~~~~~~~~
combo.cpp:66:38: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |         if (ask1.size() + ask.size() > mxlen){
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
combo.cpp:51:13: warning: unused variable 'add' [-Wunused-variable]
   51 |         int add = 0;
      |             ^~~
combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < can.size(); ++i)
      |                     ~~^~~~~~~~~~~~
combo.cpp:98:27: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |     while(base.size() + 1 != n){
      |           ~~~~~~~~~~~~~~~~^~~~
combo.cpp:102:46: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |         while(check(l, n * 4, base).S.size() > l) ++l;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
combo.cpp:99:13: warning: unused variable 'ost' [-Wunused-variable]
   99 |         int ost = n - base.size();
      |             ^~~
combo.cpp:113:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |     while(base.size() != n){
      |           ~~~~~~~~~~~~^~~~
combo.cpp:120:37: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |         if (ask.size() + dop.size() <= 4 * n || base.size() == n){
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
combo.cpp:120:61: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |         if (ask.size() + dop.size() <= 4 * n || base.size() == n){
      |                                                 ~~~~~~~~~~~~^~~~
combo.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             if (otv == base.size())
      |                 ~~~~^~~~~~~~~~~~~~
combo.cpp:126:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             if (otv == 1 + base.size())
      |                 ~~~~^~~~~~~~~~~~~~~~~~
combo.cpp:134:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |                 if (press(ask) == base.size() + 1){
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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