| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 44597 |
2018-04-03T15:40:40 Z |
aome |
Library (JOI18_library) |
C++17 |
|
705 ms |
720 KB |
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> vec, res, res1, res2;
int query() {
bool flag = 0;
for (int i = 0; i < n; ++i) flag |= vec[i];
if (!flag) return 0;
return Query(vec);
}
int calc(int x, int y) {
int ret = 0;
vec.assign(n, 0);
for (int i = 0; i <= x; ++i) vec[i] = 1;
vec[y] = 1, ret += query();
vec[y] = 0, ret -= query();
return ret;
}
void Solve(int _n) {
n = _n;
if (n == 1) {
res.push_back(1), Answer(res); return;
}
int cur = 0, nxt = 0;
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (calc(mid, cur) == 1) l = mid;
else r = mid - 1;
}
nxt = l + 1;
int tmp = nxt;
while (1) {
int prv = cur;
cur = nxt, nxt = 0;
res1.push_back(cur + 1);
for (int j = 0; j < 10; ++j) {
int ret = 0;
vec.assign(n, 0);
for (int k = 0; k < n; ++k) {
if (!(k >> j & 1)) vec[k] = 1;
}
vec[prv] = 1;
vec[cur] = 1, ret += query();
vec[cur] = 0, ret -= query();
nxt += (ret == 0) << j;
}
if (nxt == 1023) break;
}
cur = tmp, nxt = 0;
while (1) {
int prv = cur;
cur = nxt, nxt = 0;
res2.push_back(cur + 1);
if (res1.size() + res2.size() == n) break;
for (int j = 0; j < 10; ++j) {
int ret = 0;
vec.assign(n, 0);
int x = prv >> j & 1;
for (int k = 0; k < n; ++k) {
if ((k >> j & 1) == x) vec[k] = 1;
}
vec[cur] = 1, ret += query();
vec[cur] = 0, ret -= query();
nxt += (x ^ (ret == 0)) << j;
}
}
reverse(res1.begin(), res1.end());
res = res1;
for (auto i : res2) res.push_back(i);
Answer(res);
}
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:61:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (res1.size() + res2.size() == n) break;
~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
304 KB |
Output is correct |
| 2 |
Correct |
59 ms |
564 KB |
Output is correct |
| 3 |
Correct |
48 ms |
564 KB |
Output is correct |
| 4 |
Correct |
45 ms |
564 KB |
Output is correct |
| 5 |
Correct |
62 ms |
564 KB |
Output is correct |
| 6 |
Correct |
65 ms |
640 KB |
Output is correct |
| 7 |
Correct |
60 ms |
640 KB |
Output is correct |
| 8 |
Correct |
66 ms |
640 KB |
Output is correct |
| 9 |
Correct |
57 ms |
640 KB |
Output is correct |
| 10 |
Correct |
36 ms |
640 KB |
Output is correct |
| 11 |
Correct |
2 ms |
640 KB |
Output is correct |
| 12 |
Correct |
2 ms |
640 KB |
Output is correct |
| 13 |
Correct |
2 ms |
640 KB |
Output is correct |
| 14 |
Correct |
3 ms |
640 KB |
Output is correct |
| 15 |
Correct |
8 ms |
640 KB |
Output is correct |
| 16 |
Correct |
9 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
304 KB |
Output is correct |
| 2 |
Correct |
59 ms |
564 KB |
Output is correct |
| 3 |
Correct |
48 ms |
564 KB |
Output is correct |
| 4 |
Correct |
45 ms |
564 KB |
Output is correct |
| 5 |
Correct |
62 ms |
564 KB |
Output is correct |
| 6 |
Correct |
65 ms |
640 KB |
Output is correct |
| 7 |
Correct |
60 ms |
640 KB |
Output is correct |
| 8 |
Correct |
66 ms |
640 KB |
Output is correct |
| 9 |
Correct |
57 ms |
640 KB |
Output is correct |
| 10 |
Correct |
36 ms |
640 KB |
Output is correct |
| 11 |
Correct |
2 ms |
640 KB |
Output is correct |
| 12 |
Correct |
2 ms |
640 KB |
Output is correct |
| 13 |
Correct |
2 ms |
640 KB |
Output is correct |
| 14 |
Correct |
3 ms |
640 KB |
Output is correct |
| 15 |
Correct |
8 ms |
640 KB |
Output is correct |
| 16 |
Correct |
9 ms |
640 KB |
Output is correct |
| 17 |
Correct |
568 ms |
640 KB |
Output is correct |
| 18 |
Correct |
554 ms |
640 KB |
Output is correct |
| 19 |
Correct |
548 ms |
640 KB |
Output is correct |
| 20 |
Correct |
513 ms |
700 KB |
Output is correct |
| 21 |
Correct |
431 ms |
716 KB |
Output is correct |
| 22 |
Correct |
528 ms |
720 KB |
Output is correct |
| 23 |
Correct |
553 ms |
720 KB |
Output is correct |
| 24 |
Correct |
212 ms |
720 KB |
Output is correct |
| 25 |
Correct |
546 ms |
720 KB |
Output is correct |
| 26 |
Correct |
472 ms |
720 KB |
Output is correct |
| 27 |
Correct |
164 ms |
720 KB |
Output is correct |
| 28 |
Correct |
572 ms |
720 KB |
Output is correct |
| 29 |
Correct |
540 ms |
720 KB |
Output is correct |
| 30 |
Correct |
705 ms |
720 KB |
Output is correct |
