oj.uz

Submission #371222

# Submission time Handle Problem Language Result Execution time Memory
371222 2021-02-26T06:44:24 Z ja_kingy Circus (Balkan15_CIRCUS) C++14
17 / 100
 4000 ms 524292 KB 
#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> mnstk;
vector<int> _P;
int N, M;

void init(int _N, int _M, int P[]){
    N = _N;
    M = _M;
    _P.insert(_P.end(), P, P+N);
}

bool can_do(int k, int x, vector<int>& P) {
    vector<int> mx(N+2);
    priority_queue<pii> pq;
    mx[x] = k;
    pq.emplace(k, x);
    while (pq.size()) {
        pii u = pq.top(); pq.pop();
        // cout << u.first << ' ' << u.second << '\n';
        if (u.second == N+1) return true;
        if (mx[u.second] != u.first) continue;
        for (int l = u.second - 1; l >= 0 && P[u.second] - P[l] <= u.first; l--) {
            int nw = P[u.second] - P[l];
            if (nw > mx[l]) {
                mx[l] = nw;
                pq.emplace(nw, l);
            }
        }
        for (int r = u.second + 1; r < N + 2 && P[r] - P[u.second] <= u.first; r++) {
            int nw = P[r] - P[u.second];
            if (nw > mx[r]) {
                mx[r] = nw;
                pq.emplace(nw, r);
            }            
        }        
    }
    return false;
}

int minLength(int D) {
    vector<int> P = _P;
    P.push_back(D);
    P.push_back(M);
    sort(P.begin(), P.end());
    int x = find(P.begin(), P.end(), D) - P.begin();
    int lo = 1, hi = M, mid;
    while (lo != hi) {
        mid = lo + hi >> 1;
        if (can_do(mid, x, P)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

Compilation message

circus.cpp: In function 'int minLength(int)':
circus.cpp:51:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         mid = lo + hi >> 1;
      |               ~~~^~~~
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 2076 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 512 KB Output is correct
2 Correct 16 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 14 ms 364 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 512 KB Output is correct
2 Correct 16 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 14 ms 364 KB Output is correct
5 Execution timed out 4098 ms 6660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 512 KB Output is correct
2 Correct 16 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 14 ms 364 KB Output is correct
5 Execution timed out 4098 ms 6660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 2076 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 2076 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -