Submission #575547

#	Time	Username	Problem	Language	Result	Execution time	Memory
575547		nghiass001	Finding Routers (IOI20_routers)	C++17	98.82 / 100	8 ms	312 KiB

routers

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
int sz, ans[1005], rangel[1005], ranger[1005];

int use_detector(int x);

void update(int tmp, int x) {
    REP(i, 0, tmp) ranger[i] = min(ranger[i], x - 1);
    REP(i, tmp + 1, sz) rangel[i] = max(rangel[i], x + 1);
    rangel[tmp] = x;
}

int ask(int x) {
    int tmp = use_detector(x);
    update(tmp, x);
    return tmp;
}

void solve(int l, int r, int num) {
    int mid;
    while (l < r) {
        mid = (l + r + 1) / 2;
        if (ask(mid) > num) r = mid - 1;
        else l = mid;
    }
    ans[num] = l;
}

vector<int> find_routers(int l, int n, int q) {
    sz = n;
    REP(i, 0, n) ranger[i] = l;
    REP(i, 0, n - 1) {
        solve(rangel[i], ranger[i], i);
    }
    vector<int> List(n, 0);
    REP(i, 1, n) List[i] = ans[i - 1] * 2 - List[i - 1];
    return List;
}

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