Submission #575550

#	Time	Username	Problem	Language	Result	Execution time	Memory
575550		nghiass001	Finding Routers (IOI20_routers)	C++17	100 / 100	1 ms	340 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);
    return tmp;
}

void solve(int l, int r, int numx, int numy) {
    if (l > r) return;
    if (numx == numy) {
        ans[numx] = r;
        return;
    }
    int mid = (l + r) / 2;
    int tmp = ask(mid);
    solve(l, mid - 1, numx, tmp);
    ans[tmp] = mid;
    solve(mid + 1, r, tmp, numy);
}

vector<int> find_routers(int l, int n, int q) {
    solve(0, l, 0, n - 1);
    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: 40 / 40