Submission #371222

#	Time	Username	Problem	Language	Result	Execution time	Memory
371222		ja_kingy	Circus (Balkan15_CIRCUS)	C++14	17 / 100	4098 ms	524292 KiB

circus

#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 (stderr)

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
• Subtask 2: 17 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9