| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 713996 |
2023-03-23T12:40:19 Z |
vjudge1 |
ICC (CEOI16_icc) |
C++17 |
|
0 ms |
0 KB |
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
void init(int T) {
/* ... */
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r){
return uniform_int_distribution <int> (l, r) (rng);
}
double randdouble(double l, double r){
return uniform_real_distribution <double> (l, r) (rng);
}
const int N = 720;
const int K = 6;
bitset <N> f;
int p[N][K];
int pos[N][K + 1];
int askmin(int i, int j, int k){
int cti = 0, ctj = 0, ctk = 0;
for(int id = 0; id < N; ++id){
if (!f[id]) continue;
vector <pair<int, int>> v;
v.push_back({pos[id][i], i});
v.push_back({pos[id][j], j});
v.push_back({pos[id][k], k});
sort(v.begin(), v.end());
if (v[0].second == i) cti++;
if (v[0].second == j) ctj++;
if (v[0].second == k) ctk++;
}
return max({cti, ctj, ctk});
}
int askmed(int i, int j, int k){
int cti = 0, ctj = 0, ctk = 0;
for(int id = 0; id < N; ++id){
if (!f[id]) continue;
vector <pair<int, int>> v;
v.push_back({pos[id][i], i});
v.push_back({pos[id][j], j});
v.push_back({pos[id][k], k});
sort(v.begin(), v.end());
if (v[1].second == i) cti++;
if (v[1].second == j) ctj++;
if (v[1].second == k) ctk++;
}
return max({cti, ctj, ctk});
}
int askmax(int i, int j, int k){
int cti = 0, ctj = 0, ctk = 0;
for(int id = 0; id < N; ++id){
if (!f[id]) continue;
vector <pair<int, int>> v;
v.push_back({pos[id][i], i});
v.push_back({pos[id][j], j});
v.push_back({pos[id][k], k});
sort(v.begin(), v.end());
if (v[2].second == i) cti++;
if (v[2].second == j) ctj++;
if (v[2].second == k) ctk++;
}
return max({cti, ctj, ctk});
}
int asklb(int i, int j, int k, int b){
int cti = 0, ctj = 0, ctk = 0;
for(int id = 0; id < N; ++id){
if (!f[id]) continue;
vector <pair<int, int>> v;
v.push_back({pos[id][i], i});
v.push_back({pos[id][j], j});
v.push_back({pos[id][k], k});
v.push_back({pos[id][b], b});
sort(v.begin(), v.end());
int pb;
for(int i = 0; i < 4; ++i){
if (v[i].second == b) pb = i;
}
if (pb == 3) pb = -1;
if (v[pb + 1].second == i) cti++;
if (v[pb + 1].second == j) ctj++;
if (v[pb + 1].second == k) ctk++;
}
return max({cti, ctj, ctk});
}
void upd_lb(int i, int j, int k, int b){
int val = getNextLightest(i, j, k, b);
for(int id = 0; id < N; ++id){
if (!f[id]) continue;
vector <pair<int, int>> v;
v.push_back({pos[id][i], i});
v.push_back({pos[id][j], j});
v.push_back({pos[id][k], k});
v.push_back({pos[id][b], b});
sort(v.begin(), v.end());
int pb;
for(int i = 0; i < 4; ++i){
if (v[i].second == b) pb = i;
}
if (pb == 3){
pb = -1;
}
if (v[pb + 1].second != val) f[id] = 0;
}
}
void upd(array<int, 5> mi){
int i = mi[1], j = mi[2], k = mi[3], type = mi[4];
int val;
if (type == 0) val = getLightest(i, j, k);
if (type == 1) val = getMedian(i, j, k);
if (type == 2) val = getHeaviest(i, j, k);
if (type >= 100){
type -= 100;
upd_lb(i, j, k, type);
return;
}
for(int id = 0; id < N; ++id){
if (!f[id]) continue;
vector <pair<int, int>> v;
v.push_back({pos[id][i], i});
v.push_back({pos[id][j], j});
v.push_back({pos[id][k], k});
sort(v.begin(), v.end());
if (v[type].second != val) f[id] = 0;
}
}
void orderCoins() {
vector <int> per;
for(int i = 1; i <= K; ++i) per.push_back(i);
int ct = 0;
do{
f[ct] = true;
for(int i = 0; i < K; ++i){
p[ct][i] = per[i];
pos[ct][per[i]] = i;
}
++ct;
}while(next_permutation(per.begin(), per.end()));
while ((int)f.count() > 1){
array<int, 5> mi = {INF, INF, INF, INF, INF};
vector <array<int, 5>> candidate;
for(int i = 1; i <= 6; ++i){
for(int j = i + 1; j <= 6; ++j){
for(int k = j + 1; k <= 6; ++k){
if (askmin(i, j, k) < mi[0]){
candidate.clear();
candidate.push_back({askmin(i, j, k), i, j, k, 0});
} else if (askmin(i, j, k) == mi[0]){
candidate.push_back({askmin(i, j, k), i, j, k, 0});
}
if (askmed(i, j, k) < mi[0]){
candidate.clear();
candidate.push_back({askmed(i, j, k), i, j, k, 1});
} else if (askmed(i, j, k) == mi[0]){
candidate.push_back({askmed(i, j, k), i, j, k, 1});
}
if (askmax(i, j, k) < mi[0]){
candidate.clear();
candidate.push_back({askmax(i, j, k), i, j, k, 2});
} else if (askmax(i, j, k) == mi[0]){
candidate.push_back({askmax(i, j, k), i, j, k, 2});
}
mi = min(mi, {askmin(i, j, k), i, j, k, 0});
mi = min(mi, {askmed(i, j, k), i, j, k, 1});
mi = min(mi, {askmax(i, j, k), i, j, k, 2});
for(int b = 1; b <= 6; ++b){
if (b == i || b == j || b == k) continue;
if (asklb(i, j, k, b) < mi[0]){
candidate.clear();
candidate.push_back({asklb(i, j, k, b), i, j, k, b + 100});
} else {
candidate.push_back({asklb(i, j, k, b), i, j, k, b + 100});
}
mi = min(mi, {asklb(i, j, k, b), i, j, k, b + 100});
}
}
}
}
int r = randint(0, (int)candidate.size() - 1);
upd(candidate[r]);
}
int W[6] = {0, 0, 0, 0, 0, 0};
for(int id = 0; id < N; ++id){
if (!f[id]) continue;
for(int i = 0; i < 6; ++i) W[i] = p[id][i];
}
answer(W);
}
Compilation message
icc.cpp:1:10: fatal error: scales.h: No such file or directory
1 | #include "scales.h"
| ^~~~~~~~~~
compilation terminated.
