#include <bits/stdc++.h>
#include "routers.h"
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
using namespace std;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;
static int l, n, q;
static std::vector<int> p;
static std::vector<int> answer;
static int queries = 0;
const int MAX = 100010;
int arr[MAX], fir[MAX], cnt[MAX], res[MAX];
int lowerBound(int lo, int hi, int tar) { // tar + 1반환
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
int chk = use_detector(mid);
if (chk < tar) lo = mid;
else hi = mid;
}
return hi;
}
void divide(int lo, int hi) {
int mid = (lo + hi) / 2;
int tar = use_detector(mid);
int lft = lowerBound(lo, hi, tar);
int rgt = lowerBound(lo, hi, tar + 1) - 1;
arr[lft] = tar;
arr[rgt] = tar;
if (lo + 1 < lft) divide(lo, lft - 1);
if (rgt + 1 < hi) divide(rgt, hi);
}
std::vector<int> find_routers(int l, int n, int q) {
for (int i = 0; i < MAX; i++) arr[i] = -1;
divide(-1, l + 1);
for (int i = 1; i < l; i++) arr[i] = max(arr[i], arr[i - 1]);
for (int i = 0; i < l + 1; i++) {
if (arr[i] >= 0) cnt[arr[i]]++;
if (i >= 1 && arr[i] > arr[i - 1]) fir[arr[i]] = i;
}
fir[0] = 0;
res[0] = 0;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] + (cnt[i - 1] - 1) * 2;
cnt[i] -= cnt[i - 1] - 2;
}
vector<int> v;
for (int i = 0; i < n; i++) v.push_back(res[i]);
return v;
}
Compilation message
routers.cpp:15:12: warning: 'queries' defined but not used [-Wunused-variable]
15 | static int queries = 0;
| ^~~~~~~
routers.cpp:12:18: warning: 'q' defined but not used [-Wunused-variable]
12 | static int l, n, q;
| ^
routers.cpp:12:15: warning: 'n' defined but not used [-Wunused-variable]
12 | static int l, n, q;
| ^
routers.cpp:12:12: warning: 'l' defined but not used [-Wunused-variable]
12 | static int l, n, q;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
600 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
604 KB |
Output is correct |
| 10 |
Correct |
1 ms |
792 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
604 KB |
Output is correct |
| 15 |
Correct |
1 ms |
756 KB |
Output is correct |
| 16 |
Correct |
1 ms |
604 KB |
Output is correct |
| 17 |
Correct |
1 ms |
604 KB |
Output is correct |
| 18 |
Correct |
1 ms |
604 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
600 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
600 KB |
Output is correct |
| 10 |
Correct |
1 ms |
832 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
836 KB |
Output is correct |
| 15 |
Correct |
1 ms |
604 KB |
Output is correct |
| 16 |
Correct |
1 ms |
604 KB |
Output is correct |
| 17 |
Correct |
1 ms |
604 KB |
Output is correct |
| 18 |
Correct |
1 ms |
604 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Too many queries used |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2 ms |
856 KB |
Partial score |
| 2 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 3 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 4 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 5 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 6 |
Partially correct |
2 ms |
856 KB |
Partial score |
| 7 |
Partially correct |
2 ms |
1056 KB |
Partial score |
| 8 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 9 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 10 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Partially correct |
2 ms |
828 KB |
Partial score |
| 13 |
Correct |
1 ms |
832 KB |
Output is correct |
| 14 |
Partially correct |
2 ms |
856 KB |
Partial score |
| 15 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 16 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 17 |
Partially correct |
2 ms |
1112 KB |
Partial score |
| 18 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 19 |
Partially correct |
2 ms |
860 KB |
Partial score |
| 20 |
Partially correct |
2 ms |
1112 KB |
Partial score |
| 21 |
Partially correct |
2 ms |
860 KB |
Partial score |
