Submission #1201108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201108		Gray	Finding Routers (IOI20_routers)	C++20	100 / 100	1 ms	328 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
#define ll int // 🗿

using namespace std;


void gen(ll l, ll r, ll cl, ll cr, vector<ll> &bound){
    // cout << l << "-" << r << " : " << cl << "-" << cr << endl;
    if (cl>cr) return;
    if (l>=r){
        for (ll i=cl; i<=cr; i++) bound[i]=max(bound[i], l);
    }else{
        ll m = (l+r)/2;
        ll idx = use_detector(m+1);
        bound[idx]=max(bound[idx], m+1);
        // cout << idx << " <- " << m << endl;
        gen(l, m, cl, idx-1, bound);
        gen(m+1, r, idx, cr, bound);
    }
}

vector<ll> case1(ll length, ll n, ll q){
    vector<ll> bounds(n, 0);
    gen(0, length, 0, n-2, bounds);
    // for (ll i=0; i<n; i++) cout << bounds[i] << " ";
    // cout << endl;
    vector<ll> ans = {0};
    for (ll i=0; i<n-1; i++){
        ans.push_back(ans.back()+2*(bounds[i]-ans.back()));
    }
    return ans;
}

vector<ll> case2(ll len, ll n, ll q){
    ll l=0, r=len;
    while (l+1<r){
        ll mid = (l+r)/2;
        ll idx = use_detector(mid);
        if (idx==0) l=mid;
        else r=mid;
    }
    return {0, l*2};
}

vector<int> find_routers(int l, int n, int q) {
    if (n==2) return case2(l, n, q);
	return case1(l, n, q);
}

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