Submission #1200443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200443		Nelt	Finding Routers (IOI20_routers)	C++20	100 / 100	1 ms	332 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

std::vector<int> find_routers(int L, int n, int q)
{
    vector<int> ans;
    ans.push_back(0);
    ll B = n == 2 ? 2e5 : 64;
    for (ll i = 1; i <= L; i += B)
    {
        ll j = min((ll)L, i + B - 1);
        ll l, r, x = use_detector(min((ll)L, j + 1));
        bool ok;
        while (ans.size() < n and ans.back() + 1 <= j and x != ans.size() - 1)
        {
            l = max(i, (ll)ans.back() + 1), r = j;
            while (l <= r)
            {
                ll mid = (l + r) >> 1;  
                if (use_detector(mid) < ans.size())
                    l = mid + 1;
                else
                    r = mid - 1;
            }   
            ans.push_back(2 * r - ans.back());
        }
    }
    return ans;
}

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