This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "avoid.h"
#include <vector>
using namespace std;
const int N = 1000, LN = 10, L = 26;
typedef vector<int> vi;
typedef pair<int, int> pi;
int count(int b) {
return b == 0 ? 0 : count(b & b - 1) + 1;
}
pi scout(int q, int b) {
if (q == 10) {
for (int l = 0; l < LN; l++) {
vi ii;
for (int i = 0; i < N; i++)
if ((i >> l & 1) != 0)
ii.push_back(i + 1);
send(ii);
}
vi cc = wait();
int i = 0;
for (int l = 0; l < LN; l++)
if (cc[l])
i |= 1 << l;
return { i + 1, i + 1 };
} else if (q == 20) {
int lower = 0, upper = N;
while (upper - lower > 1) {
int m = (lower + upper) / 2;
vi ii;
for (int i = lower; i < m; i++)
ii.push_back(i + 1);
send(ii);
if (wait()[0])
upper = m;
else
lower = m;
}
int i_ = lower;
lower = 0, upper = N + 1;
while (upper - lower > 1) {
int m = (lower + upper) / 2;
vi ii;
for (int i = lower; i < m; i++)
if (i != i_)
ii.push_back(i + 1);
if (ii.size() == 0) {
lower = m;
continue;
}
send(ii);
if (wait()[0])
upper = m;
else
lower = m;
}
int j_ = lower;
if (j_ == N)
j_ = i_;
return { i_ + 1, j_ + 1 };
} else {
vi bb(N), ij(1 << L, -1);
for (int j = 0, b = 0; j < N; j++) {
bool good = false;
while (b < 1 << L) {
bb[j] = b++;
if (count(bb[j]) != L / 3)
continue;
good = true;
for (int i = 0; i <= j; i++)
if (ij[bb[i] | bb[j]] != -1) {
good = false;
break;
}
if (good) {
for (int i = 0; i <= j; i++)
ij[bb[i] | bb[j]] = i * N + j;
break;
}
}
if (!good)
return { -1, -1 };
}
for (int l = 0; l < L; l++) {
vi ii;
for (int i = 0; i < N; i++)
if ((bb[i] >> l & 1) != 0)
ii.push_back(i + 1);
send(ii);
}
vi cc = wait();
int b = 0;
for (int l = 0; l < L; l++)
if (cc[l])
b |= 1 << l;
int i = ij[b] / N, j = ij[b] % N;
return { i + 1, j + 1 };
}
}
Compilation message (stderr)
avoid.cpp: In function 'int count(int)':
avoid.cpp:12:34: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
12 | return b == 0 ? 0 : count(b & b - 1) + 1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |