結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
👑  wanui
|
| 提出日時 | 2025-12-25 01:02:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 77 ms / 5,000 ms |
| コード長 | 6,273 bytes |
| 記録 | |
| コンパイル時間 | 2,852 ms |
| コンパイル使用メモリ | 227,804 KB |
| 実行使用メモリ | 26,072 KB |
| スコア | 9,939,621 |
| 平均クエリ数 | 603.79 |
| 最終ジャッジ日時 | 2025-12-25 01:04:35 |
| 合計ジャッジ時間 | 13,626 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
// clang-format off
using namespace std;
#define debug1(a) { cerr<<#a<<":"<<a<<endl; }
#define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }
#define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }
#define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }
// clang-format on
using pii = pair<int, int>;
const int L = 5;
const int N = 30;
const int D = 10;
const int LOCAL = 0;
namespace Judge {
class Judge {
public:
vector<vector<int>> local_ans;
vector<int> success;
vector<pair<vector<int>, vector<pii>>> history;
void initialize_ans() {
if (!LOCAL) return;
std::random_device seed_gen;
mt19937 engine;
engine.seed(seed_gen());
local_ans.clear();
for (int i = 0; i < N; i++) {
while (true) {
vector<int> ten(10);
iota(ten.begin(), ten.end(), 0);
shuffle(ten.begin(), ten.end(), engine);
vector<int> five(5);
for (int k = 0; k < 5; k++) {
five[k] = ten[k];
}
bool ok = true;
for (auto e : local_ans) {
if (e == five) ok = false;
}
if (ok) {
local_ans.push_back(five);
break;
}
}
}
success = vector<int>(N);
}
vector<pii> request(vector<int> q) {
for (int k = 0; k < 5; k++) {
cout << q[k];
}
cout << endl;
vector<pii> res(N);
if (LOCAL) {
for (int i = 0; i < N; i++) {
if (success[i]) {
res[i] = {5, 0};
continue;
}
int h = 0;
int b = 0;
for (int k = 0; k < 5; k++) {
for (int l = 0; l < 5; l++) {
if (q[k] == local_ans[i][l]) {
if (k == l) {
h++;
} else {
b++;
}
}
}
}
res[i] = {h, b};
if (res[i] == pii{5, 0}) {
success[i] = 1;
}
}
sort(res.begin(), res.end());
} else {
for (int i = 0; i < N; i++) {
cin >> res[i].first >> res[i].second;
}
}
history.push_back({q, res});
return res;
}
};
} // namespace Judge
class Solver {
public:
vector<vector<int>> get_candidate() {
auto check = [](string s) {
sort(s.begin(), s.end());
for (int i = 1; i < s.size(); i++) {
if (s[i - 1] == s[i]) {
return false;
}
}
return true;
};
vector<string> s;
for (int i = 0; i <= 99999; i++) {
int v = i;
string cur;
for (int j = 0; j < 5; j++) {
cur.push_back('0' + v % 10);
v /= 10;
}
reverse(cur.begin(), cur.end());
if (check(cur)) {
s.push_back(cur);
}
}
vector<vector<int>> res;
for (auto &nx : s) {
vector<int> q = {nx[0] - '0', nx[1] - '0', nx[2] - '0', nx[3] - '0', nx[4] - '0'};
res.push_back(q);
}
return res;
}
void solve() {
mt19937 engine;
{
std::random_device seed_gen;
engine.seed(seed_gen());
}
auto judge = Judge::Judge();
judge.initialize_ans();
// vector<vector<int>> candidate = get_candidate();
set<vector<int>> checked;
int success = 0;
tuple<int, pii, vector<int>> prev = {-1, {-1, -1}, {0, 1, 2, 3, 4}};
while (true) {
// debug1(judge.history.size());
vector<int> q;
for (int it = 0; it < 10000; it++) {
q = get<2>(prev);
if (!judge.history.size()) break;
auto best_match = get<1>(prev);
if (it >= 100) {
vector<int> ten(10);
iota(ten.begin(), ten.end(), 0);
shuffle(ten.begin(), ten.end(), engine);
vector<int> five(5);
for (int k = 0; k < 5; k++) {
five[k] = ten[k];
}
q = five;
} else if (best_match.first + best_match.second == L) {
int si = 0;
int sj = 0;
while (si == sj) {
si = engine() % L;
sj = engine() % L;
}
swap(q[si], q[sj]);
} else {
int k = engine() % L;
int d = engine() % D;
q[k] = d;
}
if (checked.count(q)) continue;
set<int> qs;
for (auto e : q) qs.insert(e);
if (qs.size() != 5) continue;
break;
}
checked.insert(q);
auto res = judge.request(q);
int now_success = 0;
pair<int, pii> best = {-1, {-1, -1}};
for (int i = 0; i < N; i++) {
int h, b;
tie(h, b) = res[i];
if (h == 5) {
now_success++;
} else {
int f = h * 10 + b * 9; // TODO
best = max(best, {f, {h, b}});
}
}
if (now_success == N) {
debug1(judge.history.size());
return;
}
assert(success <= now_success);
if (success < now_success || best.first >= get<0>(prev)) {
prev = {best.first, best.second, q};
}
success = now_success;
}
}
};
int main() {
Solver().solve();
return 0;
}