Submission #301640

#	Time	Username	Problem	Language	Result	Execution time	Memory
301640		kevinsogo	Finding Routers (IOI20_routers)	C++17	100 / 100	2 ms	512 KiB

routers

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

vector<int> maxs;
void solve(int p1, int p2, int i1, int i2) {
    if (i1 == i2 || p2 - p1 <= 1) return;
    int pm = p1 + p2 >> 1;
    int im = use_detector(pm);
    maxs[im] = max(maxs[im], pm);
    solve(p1, pm, i1, im);
    solve(pm, p2, im, i2);
}

vector<int> find_routers(int l, int n, int q) {
    maxs = vector<int>(n, 1);
    solve(1, l, 0, n - 1);

    vector<int> ans(n);
    for (int i = 0; i < n - 1; i++) {
        ans[i + 1] = 2 * maxs[i] - ans[i];
    }
    return ans;
}

Compilation message (stderr)

routers.cpp: In function 'void solve(int, int, int, int)':
routers.cpp:8:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 |     int pm = p1 + p2 >> 1;
      |              ~~~^~~~

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