| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 127679 | hcaushi | Combo (IOI18_combo) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
This program tries to find a given combo move in as few guesses as possible.
It works by testing two passwords at a time and using it to deduce the three possible next passwords it should try.
It scores full marks in the IOI 2018.
*/
#include <iostream>
using namespace std;
std::string guess_sequence(int N) {
char[2*N] guess; // The string we're trying
char[N] suspicion2;
char not_next_letter;
char[2] next_letter;
guess[0] = 'A';
guess[N] = 'B';
for (int i=1; i<N; i++) {
guess[i] = 'B';
guess[i+N] = 'A';
}
char first_letter; // The first letter, if it's confirmed
int number_correct; // The most recent number of letters we got correct
int last_correct; // The previous number correct, also the highest number correct we've ever had
// Begin //
number_correct = press(guess);
if (number_correct == 0) {
guess[0] = 'X';
guess[N] = 'Y';
for (int i=1; i<N; i++) {
guess[i] = 'A';
guess[i+N] = 'A';
}
}
else {
for (int i = number_recorded; i < last_correct; i++)
{
suspicion2[i] = guess[i+N];
guess[i+N] = guess[i];
}
}
while (number_correct < N) {
last_correct = max(number_correct, last_correct);
number_correct = press(guess);
not_next_letter = guess[number_correct];
if ((first_letter == 'A' && not_next_letter == 'B') || (first_letter == 'B' && not_next_letter == 'A')) {
next_letter = {'X', 'Y'};
}
else if ((first_letter == 'A' && not_next_letter == 'X') || (first_letter == 'X' && not_next_letter == 'A')) {
next_letter = {'B', 'Y'};
}
else if ((first_letter == 'A' && not_next_letter == 'Y') || (first_letter == 'Y' && not_next_letter == 'A')) {
next_letter = {'B', 'X'};
}
else if ((first_letter == 'B' && not_next_letter == 'X') || (first_letter == 'X' && not_next_letter == 'B')) {
next_letter = {'A', 'Y'};
}
else if ((first_letter == 'B' && not_next_letter == 'Y') || (first_letter == 'Y' && not_next_letter == 'B')) {
next_letter = {'A', 'X'};
}
else {
next_letter = {'A', 'B'};
}
if (number_correct > last_correct) {
for (int i = last_correct; i < number_correct; i++) {
suspicion2[i-1] = guess[i+N-1];
suspicion2[i] = guess[i+N];
}
for (int i = number_correct; i < N; i++) {
guess[i] = next_letter[0];
guess[i+N] = next_letter[1];
}
}
else if (number_correct < last_correct) {
for (int i = last_correct; i < number_correct; i++) {
guess[i] = suspicion2[i];
guess[i+N] = suspicion2[i];
}
for (int i = number_correct; i < N; i++) {
guess[i] = next_letter[0];
guess[i+N] = next_letter[1];
}
}
else {
// Error //
return 1
}
}
for (int i=0; i < N; i++) {
suspicion1[i] = guess[i];
suspicion2[i] = guess[i+N];
}
press(suspicion1) == N ? return suspicion1 : return suspicion2;
}