oj.uz

Submission #329482

# Submission time Handle Problem Language Result Execution time Memory
329482 2020-11-21T10:08:37 Z dolphingarlic Circus (Balkan15_CIRCUS) C++14
49 / 100
 3067 ms 524288 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] || curr.change_cnt > 2) continue;
        for (int i = 0; i < n; i++) {
            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 1029 ms 524288 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 1152 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 1152 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 48 ms 5340 KB Output is correct
6 Correct 78 ms 9432 KB Output is correct
7 Correct 51 ms 5340 KB Output is correct
8 Correct 46 ms 5360 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 1152 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 48 ms 5340 KB Output is correct
6 Correct 78 ms 9432 KB Output is correct
7 Correct 51 ms 5340 KB Output is correct
8 Correct 46 ms 5360 KB Output is correct
9 Correct 3054 ms 9472 KB Output is correct
10 Correct 2991 ms 5944 KB Output is correct
11 Correct 2999 ms 5464 KB Output is correct
12 Correct 3067 ms 10152 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 1029 ms 524288 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 1029 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -