Submission #575546

#	Time	Username	Problem	Language	Result	Execution time	Memory
575546		nghiass001	Finding Routers (IOI20_routers)	C++17	48.76 / 100	2 ms	308 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 ans[1005];

int use_detector(int x);

int ask(int x) {
    int tmp = use_detector(x);
    ans[tmp] = max(ans[tmp], x);
    return tmp;
}

void solve(int l, int r, int numx, int numy) {
    while (numx < numy) {
        int newL = l, newR = r, mid;
        while (newL < newR) {
            mid = (newL + newR + 1) / 2;
            if (ask(mid) > numx) newR = mid - 1;
            else newL = mid;
        }
        ++numx;
        l = newL + 1;
    }
}

vector<int> find_routers(int l, int n, int q) {
    for(int i = 1; i <= l; i += 16) {
        int i2 = min(i + 15, l);
        int ll = ask(i);
        int rr = ask(i2);
        solve(i, min(i + 16, l), ll, rr);
    }
    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: 0 / 23
• Subtask 4: 11.76 / 40