Submission #1305841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305841		fafnir	Combo (IOI18_combo)	C++20	10 / 100	14 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";

string guess_sequence(int N) {
    string s;
    int len[M];

    REP(i, N) {
        random_shuffle(ABC, ABC + M);

        bool found = false;
        REP(j, M-1) {
            len[j] = press(s + ABC[j]);
        
            if (len[j] == i+1) {
                s += ABC[j];
                found = true;
                break;
            }
        }

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

#ifdef LOCAL

string SECRET = "ABXYYB";

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:24:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = char*]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   24 |         random_shuffle(ABC, ABC + M);
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
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:2:
/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: 5 / 95