Submission #339823

#	Time	Username	Problem	Language	Result	Execution time	Memory
339823		mihai145	Finding Routers (IOI20_routers)	C++14	97.29 / 100	3 ms	876 KiB

routers

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

using namespace std;

int ans[1005];

unordered_map <int, int> memo;

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

    memo[x] = use_detector(x);

    return memo[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;

    if(searchR - searchL < 1000) {
        router = (routerL + routerR) >> 1;
    } else {
        router = (rand() % (routerR - routerL + 1)) + routerL;
    }

    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) {
    srand(time(0));
    Solve(1, l - 1, 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.2928 / 40