oj.uz

Submission #329484

# Submission time Handle Problem Language Result Execution time Memory
329484 2020-11-21T10:09:47 Z dolphingarlic Circus (Balkan15_CIRCUS) C++14
49 / 100
 3073 ms 524292 KB 
#include "circus.h"

#include <bits/stdc++.h>
using namespace std;

struct State {
    int cost, idx, change_cnt;
    bool dir; // Left = 0
};

bool operator<(State A, State B) { return A.cost > B.cost; }

int n, m, p[100001], mn[100000];

void init(int N, int M, int P[]){
    n = N, m = M;
    memcpy(p, P, sizeof p);
    sort(p, p + n);
    p[n] = m;

    memset(mn, 0x3f, sizeof mn);
    priority_queue<State> pq;
    pq.push({mn[n] = 0, n, 0, false});
    while (pq.size()) {
        State curr = pq.top();
        pq.pop();
        if (curr.cost != mn[curr.idx]) continue;
        for (int i = 0; i < n; i++) {
            if (curr.change_cnt == 2 && i > curr.idx) break;
            if (abs(p[curr.idx] - p[i]) >= curr.cost && abs(p[curr.idx] - p[i]) < mn[i]) {
                bool dir = p[i] > p[curr.idx];
                pq.push({mn[i] = abs(p[curr.idx] - p[i]), i, curr.change_cnt + (curr.dir ^ dir), dir});
            }
        }
    }
}

int minLength(int D) {
    int ans = m - D;
    for (int i = 0; i < n; i++) if (abs(D - p[i]) >= mn[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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1067 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 49 ms 5340 KB Output is correct
6 Correct 71 ms 9432 KB Output is correct
7 Correct 54 ms 5340 KB Output is correct
8 Correct 49 ms 5340 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 49 ms 5340 KB Output is correct
6 Correct 71 ms 9432 KB Output is correct
7 Correct 54 ms 5340 KB Output is correct
8 Correct 49 ms 5340 KB Output is correct
9 Correct 3073 ms 9376 KB Output is correct
10 Correct 3028 ms 5960 KB Output is correct
11 Correct 3040 ms 5360 KB Output is correct
12 Correct 3046 ms 10116 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 1067 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1067 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -