#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int lb, int ub) {
return uniform_int_distribution<int>(lb, ub)(rng);
}
void Solve(int nbCouleurs, int parCouleur) {
int tot = nbCouleurs * parCouleur;
vector<bool> killed(tot);
for (int iBloc = 0; iBloc < parCouleur; ++iBloc) {
vector<int> restant;
for (int i = 0; i < tot; ++i)
if (!killed[i])
restant.push_back(i);
shuffle(restant.begin(), restant.end(), rng);
int nb = 0;
for (int p = (int)log2(restant.size()); p >= 0; --p) {
vector<int> q;
if (nb + (1 << p) > (int)restant.size())
continue;
for (int i = 0; i < nb + (1 << p); ++i)
q.push_back(restant[i] + 1);
if (Query(q) == 0)
nb += 1 << p;
}
++nb;
vector<int> crucial;
for (int i = 0; i < nb; ++i)
crucial.push_back(restant[i]);
for (int i = 0; i < (int)crucial.size(); ++i) {
vector<int> q;
for (int x : crucial)
if (x != crucial[i])
q.push_back(x + 1);
if (Query(q)) {
swap(crucial[i], crucial.back());
crucial.pop_back();
--i;
}
}
assert((int)crucial.size() == nbCouleurs);
vector<int> q;
for (int x : crucial)
q.push_back(x + 1);
Answer(q);
for (int x : crucial)
killed[x] = true;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
340 KB |
Output is correct |
2 |
Correct |
8 ms |
340 KB |
Output is correct |
3 |
Correct |
8 ms |
340 KB |
Output is correct |
4 |
Correct |
7 ms |
380 KB |
Output is correct |
5 |
Correct |
7 ms |
308 KB |
Output is correct |
6 |
Correct |
8 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
444 KB |
Output is correct |
2 |
Correct |
125 ms |
432 KB |
Output is correct |
3 |
Correct |
108 ms |
452 KB |
Output is correct |
4 |
Correct |
102 ms |
432 KB |
Output is correct |
5 |
Correct |
106 ms |
340 KB |
Output is correct |
6 |
Correct |
109 ms |
432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
586 ms |
504 KB |
Output is correct |
2 |
Correct |
512 ms |
588 KB |
Output is correct |
3 |
Correct |
598 ms |
528 KB |
Output is correct |
4 |
Correct |
546 ms |
592 KB |
Output is correct |
5 |
Correct |
543 ms |
520 KB |
Output is correct |
6 |
Correct |
621 ms |
524 KB |
Output is correct |