Submission #1200150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200150		hengliao	Finding Routers (IOI20_routers)	C++20	100 / 100	23 ms	1096 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    vector<int> ans;
    const int mxl=1e5+5;
    vector<int> rec(mxl,-1);
    map<int, int> mp;
    int query(int x){
        if(rec[x]!=-1) return rec[x];
        int re=use_detector(x);
        rec[x]=re;
        mp[x]=re;
        return re;
    }
}

void go(int l,int r,int tl,int tr){
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    int L=tl,R=tr;
    for(auto &[x, y]:mp){
        if(y<=mid){
            L=max(L, x);
        }
        else{
            R=min(R, x-1);
        }
    }
    while(L<R){
        int M=(L+R+1)/2;
        if(query(M)<=mid){
            L=M;
        }
        else{
            R=M-1;
        }
    }
    ans[mid]=L;
    go(l,mid,tl,L-2);
    go(mid+1,r,L+2,tr);
}

std::vector<int> find_routers(int l, int n, int q) {
    ans=vector<int>(n);
    go(0,n-1,0,l);
    vector<int> val(n);
    for(int i=1;i<n;i++){
        val[i]=ans[i-1]+(ans[i-1]-val[i-1]);
    }
    return val;
}

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