| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1201603 | Thanhs | Finding Routers (IOI20_routers) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
static int l, n, q;
static std::vector<int> p;
static std::vector<int> answer;
static int queries = 0;
int use_detector(int x)
{
queries++;
assert(x >= 0 && x <= l);
std::vector<int>::iterator left, right;
right = std::upper_bound(p.begin(), p.end(), x);
left = std::prev(right);
if (right == p.end()) {
return n - 1;
} else if ((x - *left) <= (*right - x)){
return std::distance(p.begin(), left);
} else {
return std::distance(p.begin(), right);
}
}
const int NM = 1e5 + 5;
vector<int> res, ans;
int GET[NM];
set<int> s;
int get(int x)
{
if (GET[x] != -1)
return GET[x];
s.insert(x);
return GET[x] = use_detector(x);
}
int cnt = 0;
void calc(int L, int R, int x)
{
if (!cnt)
return;
while (s.size() && ans[get(*s.begin())] != -1)
s.erase(s.begin());
int l = L + 1, r = (s.empty() ? R : *s.begin());
while (l < r - 1)
{
int m = l + r >> 1;
(get(m) == x ? l : r) = m;
}
int nx = L + 2 * (r - L - (get(r) > x));
ans[get(r)] = nx;
cnt--;
calc(nx, R, get(r));
}
vector<int> find_routers(int l, int n, int q)
{
ans.resize(n, -1);
ans[0] = 0;
memset(GET, -1, sizeof GET);
cnt = n - 1;
calc(0, l, 0);
return ans;
}
int main()
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
assert(scanf("%d %d %d", &l, &n, &q) == 3);
p.resize(n);
for (int i = 0; i < n; i++) {
assert(scanf("%d", &p[i]) == 1);
if (i) {
assert(p[i-1] < p[i]);
}
}
fclose(stdin);
answer = find_routers(l, n, q);
assert((int) answer.size() == n);
for (int i = 0; i < n; i++)
{
assert(answer[i] >= 0 && answer[i] <= l && answer[i] % 2 == 0);
}
for (int i = 0; i < n; i++)
{
if (i) printf(" ");
printf("%d", answer[i]);
}
printf("\n");
printf("%d\n", queries);
}