Submission #339808

#	Time	Username	Problem	Language	Result	Execution time	Memory
339808		mihai145	Finding Routers (IOI20_routers)	C++14	97.54 / 100	2 ms	512 KiB

routers

#include "routers.h"
using namespace std;

int ans[1005];

void Solve(int searchL, int searchR, int routerL, int routerR) {
    if(searchL > searchR)
        return ;

    if(routerL > routerR)
        return ;

    int router = (routerL + routerR) >> 1;

    int st = searchL, dr = searchR, sol = -1;

    int optL = dr, optR = st;

    while(st <= dr) {
        int mid = (st + dr) >> 1;

        int idx = use_detector(mid);

        if(idx <= router) {
            sol = mid;
            st = mid + 1;
        } else {
            dr = mid - 1;
        }

        if(idx == router) {
            optL = min(optL, mid);
            optR = max(optR, mid);
        }
    }

    ans[router] = sol;

    Solve(searchL, min(optL - 1, sol - 1), routerL, router - 1);
    Solve(max(optR + 1, sol + 1), searchR, router + 1, routerR);
}

std::vector<int> find_routers(int l, int n, int q) {
    Solve(1, l, 0, n - 2);

    std::vector<int> res;

    res.push_back(0);
    int lf = 0;

    for(int i = 0; i < n - 1; i++) {
        int pos = lf + 2 * (ans[i] - lf);
        res.push_back(pos);
        lf = pos;
    }

	return res;
}

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