oj.uz

Submission #1047873

# Submission time Handle Problem Language Result Execution time Memory
1047873 2024-08-07T16:54:26 Z PanosPask Circus (Balkan15_CIRCUS) C++14
100 / 100
 375 ms 31872 KB 
#include <bits/stdc++.h>
#include "circus.h"
#define mp make_pair

using namespace std;

const int INF = 1e9 + 1;

typedef pair<int, int> pi;

struct State {
    int node;
    bool forward;
    int minlen;
};

bool operator > (const State& a, const State& b)
{
    return a.minlen > b.minlen;
}

int N, M;
vector<int> p;

// nxt[i]: Next rope in the path from p[i] to M
vector<vector<int>> nxt;

/* minlen[i][fw]:
 * The minimum length of rope needed in position p[i] to reach M.
 * fw is a boolean variable denoting if the first step is forwards or backwards
 */
vector<vector<int>> minlen;
vector<int> tot;

/* change[i][fw]:
 * The maximum/minimum position at which i becomes a better choice than i - 1
 */
vector<vector<int>> change;

priority_queue<State, vector<State>, greater<State>> q;

// Test if j can become the optimal next rope in the path from p[i] to M
void test(int i, int j)
{
    if (i < 0 || i >= N) {
        return;
    }

    bool fw = (i < j);

    if (abs(p[i] - p[j]) >= tot[j] && abs(p[i] - p[j]) < minlen[i][fw]) {
        minlen[i][fw] = abs(p[i] - p[j]);
        nxt[i][fw] = j;

        q.push({i, fw, minlen[i][fw]});
    }

    // If test fails then j cannot be used as a first step anymore(in the given direction)
}

void init(int n, int m, int P[]){
    N = n;
    M = m;

    p.resize(N + 1);
    minlen.assign(N + 1, vector<int>(2, INF));
    nxt.resize(N + 1, vector<int>(2));
    tot.assign(N + 1, INF);
    change.resize(2, vector<int>(N + 1));

    for (int i = 0; i < N; i++) {
        p[i] = P[i];
    }
    p[N] = M;
    minlen[N][1] = 0;
    nxt[N][1] = N;

    sort(p.begin(), p.end());

    q.push({N, true, 0});

    while (!q.empty()) {
        int i, d;
        bool fw;
        auto res = q.top();
        q.pop();

        i = res.node;
        d = res.minlen;
        fw = res.forward;

        if (minlen[i][fw] < d) {
            continue;
        }

        tot[i] = min(tot[i], minlen[i][fw]);

        // Advance nxt[i][fw]
        int j;
        if (fw) {
            // Move more back
            j = i - 1;
        }
        else {
            // Move more front
            j = i + 1;
        }
        test(j, nxt[i][fw]);

        if (minlen[i][fw] != tot[i]) {
            continue;
        }

        // Advance i
        int p_l = upper_bound(p.begin(), p.end(), p[i] - tot[i]) - p.begin() - 1;
        int p_r = lower_bound(p.begin(), p.end(), p[i] + tot[i]) - p.begin();

        test(p_l, i);
        test(p_r, i);
    }

    // Calculate the optimal first step forwards and backwards for each possile position
    for (int i = 0; i <= N; i++) {
        change[false][i] = p[i] + tot[i];
        change[true][i] = p[i] - tot[i];
    }
    for (int i = 1; i <= N; i++) {
        // If a rope further back allows a later forward step, propagate it
        change[true][i] = max(change[true][i], change[true][i - 1]);
    }
    for (int i = N - 1; i >= 0; i--) {
        // If a rope further font allows an earlier backward step, propagate it
        change[false][i] = min(change[false][i], change[false][i + 1]);
    }
}

int minLength(int D) {
    // Find the positions that allow the best possible forward and backward steps
    int f_pos = lower_bound(change[true].begin(), change[true].end(), D) - change[true].begin();
    int b_pos = upper_bound(change[false].begin(), change[false].end(), D) - change[false].begin() - 1;

    int ans = p[f_pos] - D;
    if (b_pos >= 0) {
        ans = min(ans, D - p[b_pos]);
    }

    return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
   14 |  long long max_code;
      |            ^~~~~~~~
grader.cpp:16:7: 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:8: 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:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d", &d);
      |   ~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14172 KB Output is correct
2 Correct 47 ms 14168 KB Output is correct
3 Correct 46 ms 14428 KB Output is correct
4 Correct 48 ms 14172 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 199 ms 13648 KB Output is correct
10 Correct 163 ms 8272 KB Output is correct
11 Correct 162 ms 7464 KB Output is correct
12 Correct 199 ms 14272 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14172 KB Output is correct
2 Correct 47 ms 14168 KB Output is correct
3 Correct 46 ms 14428 KB Output is correct
4 Correct 48 ms 14172 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 51 ms 14424 KB Output is correct
14 Correct 55 ms 14524 KB Output is correct
15 Correct 55 ms 14020 KB Output is correct
16 Correct 50 ms 14168 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 14172 KB Output is correct
2 Correct 47 ms 14168 KB Output is correct
3 Correct 46 ms 14428 KB Output is correct
4 Correct 48 ms 14172 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 199 ms 13648 KB Output is correct
14 Correct 163 ms 8272 KB Output is correct
15 Correct 162 ms 7464 KB Output is correct
16 Correct 199 ms 14272 KB Output is correct
17 Correct 51 ms 14424 KB Output is correct
18 Correct 55 ms 14524 KB Output is correct
19 Correct 55 ms 14020 KB Output is correct
20 Correct 50 ms 14168 KB Output is correct
21 Correct 359 ms 25548 KB Output is correct
22 Correct 354 ms 26260 KB Output is correct
23 Correct 375 ms 29584 KB Output is correct
24 Correct 375 ms 31872 KB Output is correct