Submission #339815

#	Time	Username	Problem	Language	Result	Execution time	Memory
339815		mihai145	Finding Routers (IOI20_routers)	C++14	93.08 / 100	3 ms	748 KiB

routers

#include "routers.h"
#include <unordered_map>
#include <random>

using namespace std;

int ans[1005];

unordered_map <int, int> memo;

int Get_Detector(int x) {
    if(memo[x])
        return memo[x];

    return memo[x] = use_detector(x);
}

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

    if(routerL > routerR)
        return ;

    if(searchL == searchR) {
        ans[routerL] = searchL;
        return ;
    }

    ///int router = (routerL + routerR) >> 1;
    int router = routerL;
    if(routerR - routerL > 75) {
        router = routerL + 75;
    } else if(routerR - routerL > 20) {
        router = routerL + 20;
    }

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

    int optL = dr, optR = st;

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

        int idx = Get_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: 33.075199999999995 / 40