#include <bits/stdc++.h>
#include "circus.h"
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 3e5 + 5;
int dp[mn], p[mn], n, m;
bool vis[mn];
int node (int layer, int i) { return layer * n + i; }
void dijkstra (int source) {
priority_queue<pii> pq; pq.emplace(0, source);
for (int i = 0; i < 3 * n; i++) dp[i] = INT_MAX;
dp[source] = 0;
function<void(int,int,int)> addTransition = [&] (int from, int to, int weight) {
if (dp[from] + weight < dp[to]) {
dp[to] = dp[from] + weight;
pq.emplace(-dp[to], to);
}
};
while (pq.size()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = 1;
int layer = u / n, idx = u % n;
if (layer == 0) { /// real node
// pass to suffix layer
int sfx = lower_bound(p, p + n, dp[u] + p[idx]) - p;
if (0 <= sfx && sfx < n)
addTransition(u, node(1, sfx), p[sfx] - p[idx] - dp[u]);
// pass to prefix layer
int prf = upper_bound(p, p + n, p[idx] - dp[u]) - p - 1;
if (0 <= prf && prf < n)
addTransition(u, node(2, prf), p[idx] - p[prf] - dp[u]);
}
else if (layer == 1) { /// suffix node
// pass to real layer
addTransition(u, idx, 0);
// pass to suffix layer
if (idx + 1 < n)
addTransition(u, node(1, idx + 1), p[idx + 1] - p[idx]);
}
else if (layer == 2) { /// prefix node
// pass to real layer
addTransition(u, idx, 0);
// pass to prefix layer
if (idx - 1 >= 0)
addTransition(u, node(2, idx - 1), p[idx] - p[idx - 1]);
}
}
}
void init (int N, int M, int P[]) {
/// input processing
for (int i = 0; i < N; i++) p[i] = P[i];
p[N] = M, n = N + 1, m = M;
sort(p, p + n);
/// run dijkstra
int source = lower_bound(p, p + n, M) - p;
dijkstra(node(0, source));
}
int minLength (int D) {
int ans = INT_MAX;
for (int i = 0; i < n; i++)
if (dp[i] <= abs(p[i] - D)) ans = min(ans, abs(p[i] - D));
return ans;
}
Compilation message (stderr)
grader.cpp: In function 'int main()':
grader.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d", &P[i]);
| ~~~~~^~~~~~~~~~~~~
grader.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
grader.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf("%d", &d);
| ~~~~~^~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |