QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419790 | #4832. Telepathy | skittles1412 | 0 | 9ms | 5128kb | C++17 | 5.3kb | 2024-05-24 11:17:17 | 2024-05-24 11:17:18 |
answer
#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
bool on(int mask, int bit) {
return (mask >> bit) & 1;
}
constexpr int N = 6;
struct S {
array<int, 1 << N> arr;
array<array<array<int, 2>, N>, N> cnt;
void set_arr(int mask, int nx) {
for (int j = 0; j < N; j++) {
cnt[arr[mask]][j][on(mask, j)]--;
}
arr[mask] = nx;
for (int j = 0; j < N; j++) {
cnt[arr[mask]][j][on(mask, j)]++;
}
}
static array<array<array<int, 2>, N>, N> compute_cnt(
const array<int, 1 << N>& arr) {
array<array<array<int, 2>, N>, N> ans {};
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) {
ans[arr[i]][j][on(i, j)]++;
}
}
return ans;
}
static S c_from(const array<int, 1 << N>& arr) {
return {arr, compute_cnt(arr)};
}
};
pair<int, int> compute_opt(const S& s, int cur) {
pair<int, int> opt {};
for (int i = 0; i < N; i++) {
int ccnt = 0;
for (int j = 0; j < N; j++) {
ccnt += s.cnt[j][i][on(cur, j)];
}
opt = max(opt, {ccnt, i});
}
return opt;
}
int compute_score(const S& s) {
int ans = 0;
for (int i = 0; i < (1 << N); i++) {
ans += compute_opt(s, i).first;
}
return ans;
}
struct ScoreManager {
static void write(const S& s) {
ofstream out("output.txt");
for (auto& a : s.arr) {
out << a;
}
}
int best_score = -1, last_iter = -1;
S opt_state;
void update(int n_score, int iters, const S& s) {
if (iters - last_iter == int(1e5)) {
dbg("SAVED", best_score);
write(opt_state);
}
if (n_score <= best_score) {
return;
}
last_iter = iters;
best_score = n_score;
opt_state = s;
dbg(best_score);
}
};
struct R {
mt19937_64 cowng;
R() : cowng(chrono::steady_clock::now().time_since_epoch().count()) {}
long rint(long l, long r) {
return cowng() % (r - l + 1) + l;
}
bool rprob(double p) {
return uniform_real_distribution<double>(0, 1)(cowng) < p;
}
} R;
void sa() {
S state = S::c_from([&]() {
array<int, 1 << N> carr;
for (auto& a : carr) {
a = R.rint(0, N - 1);
}
return carr;
}());
auto accept_prob = [&](int n_score, int cur_score, double temp) -> double {
if (n_score > cur_score) {
return 1;
}
return exp((n_score - cur_score) / temp);
};
double temp = 1e5;
int cur_score = compute_score(state), iters = 0;
ScoreManager manager;
while (true) {
manager.update(cur_score, iters, state);
temp *= 0.999999;
if (++iters % 1000 == 0) {
dbg(temp, manager.best_score, cur_score);
}
int ind = R.rint(0, (1 << N) - 1), px = state.arr[ind],
nx = R.rint(0, N - 1);
state.set_arr(ind, nx);
int n_score = compute_score(state);
assert(n_score);
if (R.rprob(accept_prob(n_score, cur_score, temp))) {
cur_score = n_score;
} else {
state.set_arr(ind, px);
}
}
dbg(compute_score(state) / double(1 << (2 * N)));
}
S state = []() {
auto data =
"3255225522222222445544554400440011554455222222224455445544114430";
array<int, 1 << N> arr;
for (int i = 0; i < (1 << N); i++) {
arr[i] = data[i] - '0';
}
return S::c_from(arr);
}();
void solve_first(int kv, const string& s) {
vector<int> out;
for (int i = 0; i < kv; i++) {
int ql = i * N, cx = 0;
for (int j = 0; j < N; j++) {
cx |= (s[j] - '0') << j;
}
out.push_back(ql + state.arr[cx]);
}
for (int i = 0; i < kv; i++) {
cout << out[i] + 1 << " \n"[i == kv - 1];
}
}
void solve_second(int kv, const string& s) {
vector<int> out;
for (int i = 0; i < kv; i++) {
int ql = i * N, cx = 0;
for (int j = 0; j < N; j++) {
cx |= (s[j] - '0') << j;
}
out.push_back(ql + compute_opt(state, cx).second);
}
for (int i = 0; i < kv; i++) {
cout << out[i] + 1 << " \n"[i == kv - 1];
}
}
void solve() {
string name, s;
int n, kv;
cin >> name >> n >> kv >> s;
if (name == "Flim") {
solve_first(kv, s);
} else {
solve_second(kv, s);
}
}
int main() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 9ms
memory: 5128kb
input:
Flim 1000000 100000 1101111111100010011110111001110011110110100000111110011111111111110111110100000001001000000110111000000101110000001100111110100100000100010111001011111010001000101100101100001111011100110010010000100100100101110100100110101001001000001011111101111111001100101000010110001011011000...
output:
2 8 14 20 26 32 38 44 50 56 62 68 74 80 86 92 98 104 110 116 122 128 134 140 146 152 158 164 170 176 182 188 194 200 206 212 218 224 230 236 242 248 254 260 266 272 278 284 290 296 302 308 314 320 326 332 338 344 350 356 362 368 374 380 386 392 398 404 410 416 422 428 434 440 446 452 458 464 470 476...
input:
Flam 1000000 100000 0000001101000100010010001001011111000101010011011001010100101001110101001011001011100001011100110100011110011010100101110101101101100101111011000111001101001100010000010010101110101010111110001100110000110001001111010010000010111101110001011011101101010000111111011111100100010001...
output:
6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 108 114 120 126 132 138 144 150 156 162 168 174 180 186 192 198 204 210 216 222 228 234 240 246 252 258 264 270 276 282 288 294 300 306 312 318 324 330 336 342 348 354 360 366 372 378 384 390 396 402 408 414 420 426 432 438 444 450 456 462 468 474 4...
result:
wrong answer 50108 matched, but you need to match at least 66666 positions