oj.uz

Submission #1047840

# Submission time Handle Problem Language Result Execution time Memory
1047840 2024-08-07T16:30:10 Z PanosPask Circus (Balkan15_CIRCUS) C++14
91 / 100
 4000 ms 18324 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;

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]});
    }
}

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);

    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]
        int j;
        if (fw) {
            j = i - 1;
        }
        else {
            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);
    }
}

int minLength(int D) {
    int ans = M - D;

    for (int i = 0; i < N; i++) {
        if (abs(D - p[i]) >= tot[i]) {
            ans = min(ans, abs(D - p[i]));
        }
    }

    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 51 ms 13288 KB Output is correct
2 Correct 45 ms 13452 KB Output is correct
3 Correct 44 ms 13440 KB Output is correct
4 Correct 44 ms 13148 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 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 480 KB Output is correct
8 Correct 3 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 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 480 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 1654 ms 17196 KB Output is correct
10 Correct 1652 ms 10488 KB Output is correct
11 Correct 1648 ms 9812 KB Output is correct
12 Correct 1683 ms 18324 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13288 KB Output is correct
2 Correct 45 ms 13452 KB Output is correct
3 Correct 44 ms 13440 KB Output is correct
4 Correct 44 ms 13148 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 3 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 480 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 126 ms 13544 KB Output is correct
14 Correct 122 ms 13560 KB Output is correct
15 Correct 119 ms 13144 KB Output is correct
16 Correct 125 ms 13144 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13288 KB Output is correct
2 Correct 45 ms 13452 KB Output is correct
3 Correct 44 ms 13440 KB Output is correct
4 Correct 44 ms 13148 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 3 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 480 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 1654 ms 17196 KB Output is correct
14 Correct 1652 ms 10488 KB Output is correct
15 Correct 1648 ms 9812 KB Output is correct
16 Correct 1683 ms 18324 KB Output is correct
17 Correct 126 ms 13544 KB Output is correct
18 Correct 122 ms 13560 KB Output is correct
19 Correct 119 ms 13144 KB Output is correct
20 Correct 125 ms 13144 KB Output is correct
21 Execution timed out 4037 ms 13904 KB Time limit exceeded
22 Halted 0 ms 0 KB -