Submission #1305919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305919		fafnir	Combo (IOI18_combo)	C++20	30 / 100	12 ms	448 KiB

combo

#include <bits/stdc++.h>
#ifndef LOCAL
#include "combo.h"
#endif
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)


#ifdef LOCAL
int press(string s);
#endif


const int M = 4;
char ABC[] = "ABXY";
char REM[3];

string guess_sequence(int N) {
    string s;

    REP(i, M-1) {
        if (press(s + ABC[i])) {s += ABC[i]; break;}
    }

    if (!s.length()) {s += ABC[M-1];}

    {
        int idx = 0;
        REP(i, M) {
            if (s[0] != ABC[i]) {REM[idx++] = ABC[i];}
        }
    }

    REP(i, N-1) {
        random_shuffle(REM, REM+1);
        if (press(s + REM[0]) == (i+2)) {s += REM[0];}
        else if (press(s + REM[1]) == (i+2)) {s += REM[1];}
        else {s += REM[2];}
    }
    
    return s;
}

#ifdef LOCAL

string SECRET = "ABBBXBXBXBYYYYBBY";

int press(string p) {
    const int m = p.length();
    const int n = SECRET.length();
    int lpref = 0;

    REP(i, m) {
    
        int j = 0;
        while (j < n && i+j < m && SECRET[j] == p[i+j]) {j++;}

        lpref = max(lpref, j);
    }

    return lpref;
}

int main() {
    cout << guess_sequence(SECRET.length()) << '\n';    
}

#endif

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:36:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = char*]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   36 |         random_shuffle(REM, REM+1);
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from combo.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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