Submission #440819

#	Time	Username	Problem	Language	Result	Execution time	Memory
440819		SorahISA	Finding Routers (IOI20_routers)	C++17	73.72 / 100	2 ms	216 KiB

routers

#include "routers.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> last_place;

void cdq(int nL, int nR, int pL, int pR) {
    if (nL > nR or pL > pR) return;
    int nM = nL + nR >> 1, pM;
    int lo = pL, hi = pR, mi;
    while (lo < hi) {
        mi = lo + hi + 1 >> 1;
        if (use_detector(mi) < nM) lo = mi;
        else hi = mi - 1;
    }
    last_place[nM] = pM = lo;
    cdq(nL, nM-1, pL, pM-1), cdq(nM+1, nR, pM+1, pR);
}

vector<int> find_routers(int L, int N, int Q) {
    last_place.assign(N, -1);
    cdq(0, N-1, 0, L);
    vector<int> ans{0};
    for (int i = 1; i < N; ++i) ans.eb(2*last_place[i] - ans.back());
    return ans;
}

Compilation message (stderr)

routers.cpp: In function 'void cdq(int, int, int, int)':
routers.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int nM = nL + nR >> 1, pM;
      |              ~~~^~~~
routers.cpp:29:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         mi = lo + hi + 1 >> 1;
      |              ~~~~~~~~^~~

• Subtask 1: 16 / 16
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 36.7168 / 40