Submission #413116

#	Time	Username	Problem	Language	Result	Execution time	Memory
413116		nxteru	Finding Routers (IOI20_routers)	C++14	100 / 100	2 ms	308 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
using namespace std;
int t[1005];
void bs(int l,int r,int a,int b){
	if(a==b)return;
	int m=(l+r)/2;
	int c=use_detector(m);
	t[c]=max(t[c],m);
	if(a!=c&&m-l>1)bs(l,m,a,c);
	if(c!=b&&r-m>1)bs(m,r,c,b);
}
vector<int> find_routers(int l, int n, int q) {
	for(int i=0;i<n;i++)t[i]=-1;
	t[n-1]=l;
	bs(0,l,0,n-1);
	vector<int>ans(n);
	ans[0]=0;
	for(int i=1;i<n;i++)ans[i]=2*t[i-1]-ans[i-1];
	return ans;
}

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