| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 793346 |
2023-07-25T18:05:54 Z |
PixelCat |
Scales (IOI15_scales) |
C++14 |
|
10 ms |
412 KB |
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "scales.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;
using BS = bitset<720>;
int W[] = {1, 2, 3, 4, 5, 6};
mt19937_64 rng(7456);
uint64_t seed;
// 0 for lightest, 1 for median, 2 for heaviest, 3 for next lightest
vector<vector<int>> perm;
vector<vector<int>> options;
vector<BS> mask[4];
bool match(const vector<int> &ord, const vector<int> &opt, int res) {
if(opt[0] == 0) {
bool ok = true;
For(i, 1, 3) ok = ok && (ord[opt[i]] >= ord[opt[res]]);
return ok;
}
if(opt[0] == 2) {
bool ok = true;
For(i, 1, 3) ok = ok && (ord[opt[i]] <= ord[opt[res]]);
return ok;
}
if(opt[0] == 1) {
int owo = 0;
For(i, 1, 3) {
int dif = (ord[opt[i]] - ord[opt[res]]);
if(dif < 0) owo |= 1;
if(dif == 0) owo |= 2;
if(dif > 0) owo |= 4;
}
return owo == 7;
}
if(opt[0] == 3) {
int o[3] = {opt[1], opt[2], opt[3]};
sort(o, o + 3, [&](int x, int y){return ord[x] < ord[y];});
int idx = 0;
if(ord[opt[4]] > ord[o[2]]) idx = 0;
else if(ord[opt[4]] > ord[o[1]]) idx = 2;
else if(ord[opt[4]] > ord[o[0]]) idx = 1;
idx = o[idx];
if(idx == opt[1]) idx = 1;
else if(idx == opt[2]) idx = 2;
else if(idx == opt[3]) idx = 3;
return idx == res;
}
return false;
}
// how many possibilities remain at most?
int worstmatch(const BS &alive, const int &opt) {
int mx = 0;
For(res, 1, 3) {
mx = max(mx, (int) (alive & mask[res][opt]).count());
}
return mx;
}
int best_opt(const BS &alive) {
int mx = 1000, idx = -1;
vector<int> all_opt;
For(i, 0, sz(options) - 1) all_opt.eb(i);
shuffle(all(all_opt), rng);
// auto start = clock();
for(auto &i:all_opt) {
int k = worstmatch(alive, i);
if(k < mx) {
mx = k; idx = i;
}
}
// auto stop = clock();
// cerr << fixed << setprecision(3);
// cerr << "elapsed: " << (double)(stop - start) / CLOCKS_PER_SEC << "\n";
return idx;
}
int make_query(const vector<int> &opt) {
int x = -1;
if(opt[0] == 0) {
x = getLightest(opt[1] + 1, opt[2] + 1, opt[3] + 1);
} else if(opt[0] == 1) {
x = getMedian(opt[1] + 1, opt[2] + 1, opt[3] + 1);
} else if(opt[0] == 2) {
x = getHeaviest(opt[1] + 1, opt[2] + 1, opt[3] + 1);
} else if(opt[0] == 3) {
x = getNextLightest(opt[1] + 1, opt[2] + 1, opt[3] + 1, opt[4] + 1);
}
For(i, 1, 3) if(x == opt[i] + 1) return i;
assert(false);
return -1;
}
void remove_impossible(BS &alive, const int &opt, int res) {
alive &= mask[res][opt];
}
// #define TESTING
#ifdef TESTING
int test_all(int lim) {
map<int, int> cnt; // {# of queries, count}
For(i, 0, 719) {
For(j, 0, 5) W[j] = perm[i][j] + 1;
_setNewTest(W);
orderCoins();
cnt[_numQueries]++;
if(cnt[7] >= lim) return lim;
}
// for(auto &i:cnt) cerr << i.F << ": " << i.S << "\n";
return cnt[7];
}
uint64_t find_seed() {
int mn = 120, mni = 48763;
For(s, 408, 20000) {
seed = s;
int k = test_all(mn);
if(k < mn) {
mn = k; mni = s;
cerr << s << " " << k << "\n";
}
if(s % 300 == 299) cerr << "progress: " << (s + 1) << "\n";
}
return mni;
}
#endif
void init(int T) {
seed = 3179;
assert(T < 20);
int a[6] = {0, 1, 2, 3, 4, 5};
perm.clear();
do {
perm.eb(a, a + 6);
} while(next_permutation(a, a + 6));
For(i, 0, 5) For(j, i + 1, 5) For(k, j + 1, 5) {
options.push_back({0, i, j, k});
options.push_back({1, i, j, k});
options.push_back({2, i, j, k});
For(l, 0, 5) {
if(i == l || j == l || k == l) continue;
options.push_back({3, i, j, k, l});
}
}
For(r, 1, 3) mask[r].clear();
for(auto &opt:options) For(r, 1, 3) {
mask[r].eb();
mask[r].back().reset();
For(i, 0, 719) if(match(perm[i], opt, r)) mask[r].back()[i] = 1;
}
cerr << sz(perm) << "\n";
cerr << sz(options) << "\n";
#ifdef TESTING
// test_all();
find_seed();
#endif
}
void orderCoins() {
rng.seed(seed);
BS alive;
For(i, 0, 719) alive[i] = 1;
while(alive.count() > 1) {
int k = best_opt(alive);
int r = make_query(options[k]);
remove_impossible(alive, k, r);
// cout << sz(alive) << " " << k << " " << r << "\n" << flush;
}
int pos = -1;
For(i, 0, 719) if(alive[i]) pos = i;
vector<int> &ord = perm[pos];
For(i, 0, 5) W[ord[i]] = i + 1;
#ifndef TESTING
answer(W);
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
340 KB |
Output is correct |
| 2 |
Correct |
6 ms |
308 KB |
Output is correct |
| 3 |
Correct |
6 ms |
340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
412 KB |
Output is correct |
| 5 |
Correct |
6 ms |
340 KB |
Output is correct |
| 6 |
Correct |
6 ms |
340 KB |
Output is correct |
| 7 |
Correct |
6 ms |
404 KB |
Output is correct |
| 8 |
Correct |
6 ms |
340 KB |
Output is correct |
| 9 |
Correct |
6 ms |
408 KB |
Output is correct |
| 10 |
Correct |
6 ms |
300 KB |
Output is correct |
| 11 |
Correct |
6 ms |
340 KB |
Output is correct |
| 12 |
Correct |
6 ms |
340 KB |
Output is correct |
| 13 |
Correct |
6 ms |
340 KB |
Output is correct |
| 14 |
Correct |
6 ms |
340 KB |
Output is correct |
| 15 |
Correct |
6 ms |
340 KB |
Output is correct |
| 16 |
Correct |
6 ms |
304 KB |
Output is correct |
| 17 |
Correct |
6 ms |
308 KB |
Output is correct |
| 18 |
Correct |
6 ms |
304 KB |
Output is correct |
| 19 |
Correct |
7 ms |
340 KB |
Output is correct |
| 20 |
Correct |
6 ms |
408 KB |
Output is correct |
| 21 |
Correct |
6 ms |
340 KB |
Output is correct |
| 22 |
Correct |
6 ms |
340 KB |
Output is correct |
| 23 |
Correct |
6 ms |
340 KB |
Output is correct |
| 24 |
Correct |
6 ms |
340 KB |
Output is correct |
| 25 |
Correct |
6 ms |
340 KB |
Output is correct |
| 26 |
Correct |
6 ms |
304 KB |
Output is correct |
| 27 |
Correct |
7 ms |
340 KB |
Output is correct |
| 28 |
Correct |
6 ms |
404 KB |
Output is correct |
| 29 |
Correct |
6 ms |
340 KB |
Output is correct |
| 30 |
Correct |
6 ms |
360 KB |
Output is correct |
| 31 |
Correct |
6 ms |
340 KB |
Output is correct |
| 32 |
Correct |
6 ms |
372 KB |
Output is correct |
| 33 |
Correct |
6 ms |
340 KB |
Output is correct |
| 34 |
Correct |
6 ms |
340 KB |
Output is correct |
| 35 |
Correct |
6 ms |
340 KB |
Output is correct |
| 36 |
Correct |
6 ms |
340 KB |
Output is correct |
| 37 |
Correct |
6 ms |
304 KB |
Output is correct |
| 38 |
Correct |
6 ms |
304 KB |
Output is correct |
| 39 |
Correct |
6 ms |
340 KB |
Output is correct |
| 40 |
Correct |
10 ms |
340 KB |
Output is correct |
