#include "routers.h"
#include <bits/stdc++.h>
using namespace std;
int asked[200001];
int ask(int x){
if (asked[x] != -1)
return asked[x];
asked[x] = use_detector(x);
return asked[x];
}
vector <int> find_routers(int l, int n, int q){
vector <int> res;
res.push_back(0);
int cur = 0;
for(int i = 0; i <= l; i++)
asked[i] = -1;
if (n == 2){
int mid = 1;
for(int j = 16; j >= 0; j--){
if (mid + (1 << j) > l)
continue;
if (ask(mid + (1 << j)) == 0)
mid += (1 << j);
}
res.push_back(2 * mid);
return res;
}
for(int i = 1; i < n; i++){
int mid = cur + 1;
while (ask(min(l, mid + 64)) == i - 1)
mid = min(l, mid + 64);
for(int j = 5; j >= 0; j--){
if (mid + (1 << j) > l)
continue;
if (ask(mid + (1 << j)) == i - 1)
mid += (1 << j);
}
int nxt = 2 * mid - cur;
res.push_back(nxt);
cur = nxt;
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
768 KB |
Output is correct |
3 |
Correct |
1 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
672 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
768 KB |
Output is correct |
12 |
Correct |
1 ms |
768 KB |
Output is correct |
13 |
Correct |
1 ms |
640 KB |
Output is correct |
14 |
Correct |
1 ms |
640 KB |
Output is correct |
15 |
Correct |
1 ms |
640 KB |
Output is correct |
16 |
Correct |
1 ms |
768 KB |
Output is correct |
17 |
Correct |
1 ms |
640 KB |
Output is correct |
18 |
Correct |
1 ms |
640 KB |
Output is correct |
19 |
Correct |
1 ms |
768 KB |
Output is correct |
20 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
1 ms |
768 KB |
Output is correct |
3 |
Correct |
1 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
640 KB |
Output is correct |
7 |
Correct |
1 ms |
640 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
640 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
640 KB |
Output is correct |
12 |
Correct |
1 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
640 KB |
Output is correct |
14 |
Correct |
1 ms |
768 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
1 ms |
768 KB |
Output is correct |
17 |
Correct |
1 ms |
768 KB |
Output is correct |
18 |
Correct |
1 ms |
768 KB |
Output is correct |
19 |
Correct |
1 ms |
768 KB |
Output is correct |
20 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
1 ms |
768 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
1 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
640 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
768 KB |
Output is correct |
8 |
Correct |
1 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
640 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
640 KB |
Output is correct |
12 |
Correct |
1 ms |
640 KB |
Output is correct |
13 |
Correct |
1 ms |
768 KB |
Output is correct |
14 |
Correct |
1 ms |
640 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
1 ms |
768 KB |
Output is correct |
17 |
Correct |
1 ms |
640 KB |
Output is correct |
18 |
Correct |
1 ms |
768 KB |
Output is correct |
19 |
Correct |
1 ms |
768 KB |
Output is correct |
20 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
2 ms |
768 KB |
Output is correct |
3 |
Correct |
1 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
768 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
2 ms |
768 KB |
Output is correct |
11 |
Correct |
1 ms |
768 KB |
Output is correct |
12 |
Correct |
1 ms |
768 KB |
Output is correct |
13 |
Correct |
1 ms |
768 KB |
Output is correct |
14 |
Correct |
1 ms |
768 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
1 ms |
768 KB |
Output is correct |
17 |
Correct |
1 ms |
768 KB |
Output is correct |
18 |
Correct |
2 ms |
768 KB |
Output is correct |
19 |
Correct |
2 ms |
768 KB |
Output is correct |
20 |
Correct |
1 ms |
768 KB |
Output is correct |
21 |
Correct |
1 ms |
768 KB |
Output is correct |