Submission #1230254

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

routers

#include "routers.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <algorithm>
using namespace std;

std::vector<int> find_routers(int le, int n, int q) {
    vector<int>ans(n);
    ans[0]=0;
    vector<int>lol(n);
    vector<int>memo(le+2,-1);
    for(int i=1;i<=n-1;i++){
    	int l=0;
    	int r=le;
    	int an=-1;
    	int lol=-1;
    	while(l<=r){
    		int mid=(l+r)/2;
    		int nw;
    		if(memo[mid]==-1){
    			nw=use_detector(mid);
    			memo[mid]=nw;
			} else nw=memo[mid];
    		if(nw>i-1) r=mid-1;
    		else {
    			an=mid;
    			l=mid+1;
			}
		}
		ans[i]=an*2-ans[i-1];
	}
	return ans;
}

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