# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
950309 |
2024-03-20T07:54:00 Z |
kilkuwu |
Combo (IOI18_combo) |
C++17 |
|
15 ms |
2032 KB |
#include <bits/stdc++.h>
#ifdef LOCAL
#include <string>
std::string guess_sequence(int N);
int press(std::string p);
#else
#include "combo.h"
#endif
#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
std::string guess_sequence(int N) {
auto find_first_char = [&]() -> char {
int res = press("AB");
if (res == 0) {
res = press("X");
if (res == 0) {
return 'Y';
} else {
return 'X';
}
} else {
res = press("A");
if (res == 0) {
return 'B';
} else {
return 'A';
}
}
};
char first_char = find_first_char();
std::string char_set = "ABXY";
char_set.erase(std::find(char_set.begin(), char_set.end(), first_char));
std::vector<std::string> candidates(3, std::string(1, first_char));
if (N == 1) {
return candidates[0];
}
for (int i = 0; i < 3; i++) {
candidates[i] += char_set[i];
}
auto check_type = [&](int p) -> bool {
for (int i = 1; i < 3; i++) {
if (candidates[i][p] != candidates[0][p]) {
if (i == 2) return false;
// i == 1
if (candidates[0][p] == candidates[2][p]) {
// this guy is fraud
std::swap(candidates[1], candidates[2]);
} else {
// which means cand[0] is fraud
std::swap(candidates[0], candidates[2]);
}
return false;
}
}
return true;
};
int matched = 1; // this is the match score
for (int i = 1; i < N - 1; i++) { // N - 2 queries
dbg(i, matched);
for (int j = 0; j < 3; j++) dbg(candidates[j]);
if (check_type(i - 1)) {
std::string qstring;
qstring += candidates[0] + char_set[0];
qstring += candidates[0] + char_set[1];
qstring += candidates[1] + char_set[0];
int res = press(qstring) - matched;
if (res == 0) {
candidates[0] = candidates[2];
candidates[1] = candidates[2];
for (int j = 0; j < 3; j++) candidates[j] += char_set[j];
// this means we match another
matched++;
} else if (res == 1) {
candidates[2] = candidates[1];
candidates[0] += char_set[2];
candidates[1] += char_set[1];
candidates[2] += char_set[2];
} else {
candidates[2] = candidates[0];
candidates[0] += char_set[0];
candidates[1] += char_set[0];
candidates[2] += char_set[1];
}
} else {
std::string qstring;
qstring += candidates[1] + char_set[0];
qstring += candidates[1] + char_set[1];
qstring += candidates[1] + char_set[2];
int res = press(qstring) - matched;
if (res == 0) {
candidates[0] = candidates[2];
candidates[1] = candidates[2];
} else if (res == 1) {
candidates[1] = candidates[0];
candidates[2] = candidates[0];
} else {
candidates[0] = candidates[1];
candidates[2] = candidates[1];
}
matched += 2;
for (int j = 0; j < 3; j++) candidates[j] += char_set[j];
}
}
for (int j = 0; j < 2; j++) {
if (press(candidates[j]) == N) return candidates[j];
}
return candidates[2];
}
#ifdef LOCAL
#define nl '\n'
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include "combo.h"
namespace {
constexpr int MAX_N = 2000;
constexpr int MAX_NUM_MOVES = 8000;
int N;
std::string S;
int num_moves;
void wrong_answer(const char *MSG) {
printf("Wrong Answer: %s\n", MSG);
exit(0);
}
} // namespace
int press(std::string p) {
dbg(p);
if (++num_moves > MAX_NUM_MOVES) {
wrong_answer("too many moves");
}
int len = p.length();
if (len > 4 * N) {
wrong_answer("invalid press");
}
for (int i = 0; i < len; ++i) {
if (p[i] != 'A' && p[i] != 'B' && p[i] != 'X' && p[i] != 'Y') {
wrong_answer("invalid press");
}
}
int coins = 0;
for (int i = 0, j = 0; i < len; ++i) {
if (j < N && S[j] == p[i]) {
++j;
} else if (S[0] == p[i]) {
j = 1;
} else {
j = 0;
}
coins = std::max(coins, j);
}
dbg(coins);
return coins;
}
int main() {
char buffer[MAX_N + 1];
if (scanf("%s", buffer) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
S = buffer;
N = S.length();
num_moves = 0;
std::string answer = guess_sequence(N);
if (answer != S) {
wrong_answer("wrong guess");
exit(0);
}
printf("Accepted: %d\n", num_moves);
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
0 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
0 ms |
344 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
25 |
Correct |
0 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
0 ms |
344 KB |
Output is correct |
28 |
Correct |
0 ms |
596 KB |
Output is correct |
29 |
Correct |
0 ms |
344 KB |
Output is correct |
30 |
Correct |
1 ms |
344 KB |
Output is correct |
31 |
Correct |
0 ms |
344 KB |
Output is correct |
32 |
Correct |
0 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
344 KB |
Output is correct |
35 |
Correct |
0 ms |
344 KB |
Output is correct |
36 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
14 ms |
1364 KB |
Output is correct |
18 |
Correct |
12 ms |
1644 KB |
Output is correct |
19 |
Correct |
12 ms |
1448 KB |
Output is correct |
20 |
Correct |
11 ms |
1984 KB |
Output is correct |
21 |
Correct |
10 ms |
1148 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
436 KB |
Output is correct |
25 |
Correct |
1 ms |
436 KB |
Output is correct |
26 |
Correct |
1 ms |
440 KB |
Output is correct |
27 |
Correct |
1 ms |
436 KB |
Output is correct |
28 |
Correct |
1 ms |
440 KB |
Output is correct |
29 |
Correct |
1 ms |
440 KB |
Output is correct |
30 |
Correct |
1 ms |
444 KB |
Output is correct |
31 |
Correct |
2 ms |
600 KB |
Output is correct |
32 |
Correct |
14 ms |
1800 KB |
Output is correct |
33 |
Correct |
12 ms |
1816 KB |
Output is correct |
34 |
Correct |
12 ms |
1764 KB |
Output is correct |
35 |
Correct |
13 ms |
1312 KB |
Output is correct |
36 |
Correct |
11 ms |
1528 KB |
Output is correct |
37 |
Correct |
12 ms |
1176 KB |
Output is correct |
38 |
Correct |
12 ms |
1724 KB |
Output is correct |
39 |
Correct |
12 ms |
1544 KB |
Output is correct |
40 |
Correct |
12 ms |
1240 KB |
Output is correct |
41 |
Correct |
11 ms |
1764 KB |
Output is correct |
42 |
Correct |
10 ms |
984 KB |
Output is correct |
43 |
Correct |
13 ms |
1524 KB |
Output is correct |
44 |
Correct |
10 ms |
1596 KB |
Output is correct |
45 |
Correct |
11 ms |
1412 KB |
Output is correct |
46 |
Correct |
11 ms |
1508 KB |
Output is correct |
47 |
Correct |
11 ms |
1724 KB |
Output is correct |
48 |
Correct |
12 ms |
1164 KB |
Output is correct |
49 |
Correct |
10 ms |
1336 KB |
Output is correct |
50 |
Correct |
11 ms |
1352 KB |
Output is correct |
51 |
Correct |
11 ms |
1452 KB |
Output is correct |
52 |
Correct |
10 ms |
1324 KB |
Output is correct |
53 |
Correct |
11 ms |
1488 KB |
Output is correct |
54 |
Correct |
11 ms |
1108 KB |
Output is correct |
55 |
Correct |
13 ms |
1292 KB |
Output is correct |
56 |
Correct |
11 ms |
1508 KB |
Output is correct |
57 |
Correct |
11 ms |
1432 KB |
Output is correct |
58 |
Correct |
10 ms |
1424 KB |
Output is correct |
59 |
Correct |
11 ms |
1004 KB |
Output is correct |
60 |
Correct |
12 ms |
1812 KB |
Output is correct |
61 |
Correct |
10 ms |
1736 KB |
Output is correct |
62 |
Correct |
11 ms |
1236 KB |
Output is correct |
63 |
Correct |
14 ms |
1712 KB |
Output is correct |
64 |
Correct |
13 ms |
1452 KB |
Output is correct |
65 |
Correct |
12 ms |
2032 KB |
Output is correct |
66 |
Correct |
11 ms |
1276 KB |
Output is correct |
67 |
Correct |
11 ms |
1680 KB |
Output is correct |
68 |
Correct |
12 ms |
1700 KB |
Output is correct |
69 |
Correct |
11 ms |
1400 KB |
Output is correct |
70 |
Correct |
11 ms |
1212 KB |
Output is correct |
71 |
Correct |
15 ms |
1592 KB |
Output is correct |
72 |
Correct |
11 ms |
1428 KB |
Output is correct |
73 |
Correct |
13 ms |
1432 KB |
Output is correct |
74 |
Correct |
11 ms |
1224 KB |
Output is correct |
75 |
Correct |
11 ms |
1648 KB |
Output is correct |
76 |
Correct |
11 ms |
1916 KB |
Output is correct |
77 |
Correct |
12 ms |
1744 KB |
Output is correct |
78 |
Correct |
0 ms |
344 KB |
Output is correct |
79 |
Correct |
0 ms |
344 KB |
Output is correct |
80 |
Correct |
1 ms |
500 KB |
Output is correct |
81 |
Correct |
0 ms |
344 KB |
Output is correct |
82 |
Correct |
1 ms |
344 KB |
Output is correct |
83 |
Correct |
1 ms |
344 KB |
Output is correct |
84 |
Correct |
1 ms |
344 KB |
Output is correct |
85 |
Correct |
0 ms |
344 KB |
Output is correct |
86 |
Correct |
0 ms |
436 KB |
Output is correct |
87 |
Correct |
1 ms |
436 KB |
Output is correct |
88 |
Correct |
0 ms |
344 KB |
Output is correct |
89 |
Correct |
0 ms |
344 KB |
Output is correct |
90 |
Correct |
1 ms |
344 KB |
Output is correct |
91 |
Correct |
0 ms |
344 KB |
Output is correct |
92 |
Correct |
1 ms |
344 KB |
Output is correct |
93 |
Correct |
0 ms |
344 KB |
Output is correct |
94 |
Correct |
0 ms |
344 KB |
Output is correct |
95 |
Correct |
0 ms |
344 KB |
Output is correct |
96 |
Correct |
1 ms |
440 KB |
Output is correct |
97 |
Correct |
1 ms |
440 KB |
Output is correct |
98 |
Correct |
1 ms |
440 KB |
Output is correct |
99 |
Correct |
1 ms |
428 KB |
Output is correct |
100 |
Correct |
1 ms |
436 KB |
Output is correct |
101 |
Correct |
1 ms |
436 KB |
Output is correct |
102 |
Correct |
0 ms |
432 KB |
Output is correct |
103 |
Correct |
1 ms |
600 KB |
Output is correct |
104 |
Correct |
1 ms |
344 KB |
Output is correct |
105 |
Correct |
1 ms |
344 KB |
Output is correct |
106 |
Correct |
1 ms |
344 KB |
Output is correct |
107 |
Correct |
0 ms |
344 KB |
Output is correct |
108 |
Correct |
0 ms |
344 KB |
Output is correct |
109 |
Correct |
1 ms |
344 KB |
Output is correct |
110 |
Correct |
1 ms |
344 KB |
Output is correct |
111 |
Correct |
0 ms |
344 KB |
Output is correct |
112 |
Correct |
0 ms |
344 KB |
Output is correct |
113 |
Correct |
0 ms |
344 KB |
Output is correct |
114 |
Correct |
0 ms |
344 KB |
Output is correct |
115 |
Correct |
0 ms |
344 KB |
Output is correct |
116 |
Correct |
1 ms |
344 KB |
Output is correct |
117 |
Correct |
1 ms |
344 KB |
Output is correct |
118 |
Correct |
1 ms |
344 KB |
Output is correct |
119 |
Correct |
0 ms |
344 KB |
Output is correct |
120 |
Correct |
1 ms |
436 KB |
Output is correct |
121 |
Correct |
1 ms |
436 KB |
Output is correct |
122 |
Correct |
1 ms |
432 KB |
Output is correct |
123 |
Correct |
1 ms |
436 KB |
Output is correct |