Submission #1200245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200245		guagua0407	Finding Routers (IOI20_routers)	C++20	100 / 100	4 ms	840 KiB

routers

#include "routers.h"
//#include "grader.cpp"
#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{
    int cnt = 0;
    vector<int> ans;
    const int mxl=1e5+5;
    vector<int> rec(mxl,-1);
    vector<int> qs;
    int query(int x){
        if(rec[x]!=-1) return rec[x];
        qs.push_back(x);
        return rec[x]=use_detector(x);
    }
}

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 v:qs){
        if(rec[v]<=mid) L=max(L,v);
        else R=min(R,v);
    }
    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);
    go(mid+1,r,L,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