Submission #1201605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201605		Thanhs	Finding Routers (IOI20_routers)	C++20	100 / 100	1 ms	584 KiB

routers

#include "routers.h"
#include<bits/stdc++.h>
using namespace std;

const int NM = 1e5 + 5;

vector<int> res, ans;
int GET[NM];
set<int> s;

int get(int x)
{
    if (GET[x] != -1)
        return GET[x];
    s.insert(x);
    return GET[x] = use_detector(x);
}

int cnt = 0;

void calc(int L, int R, int x)
{
    if (!cnt)
        return;
    while (s.size() && ans[get(*s.begin())] != -1)
        s.erase(s.begin());
    int l = L + 1, r = (s.empty() ? R : *s.begin());
    while (l < r - 1)
    {
        int m = l + r >> 1;
        (get(m) == x ? l : r) = m;
    }
    int nx = L + 2 * (r - L - (get(r) > x));
    ans[get(r)] = nx;
    cnt--;
    calc(nx, R, get(r));
}

vector<int> find_routers(int l, int n, int q)
{
    ans.resize(n, -1);
    ans[0] = 0;
    memset(GET, -1, sizeof GET);
    cnt = n - 1;
    calc(0, l, 0);
    return ans;
}

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