Submission #562526

#	Time	Username	Problem	Language	Result	Execution time	Memory
562526		Iwanttobreakfree	Finding Routers (IOI20_routers)	C++17	96.83 / 100	15 ms	704 KiB

routers

#include "routers.h"
#include <vector>
using namespace std;
vector<int> guarda(100001,-1);
vector<int> find_routers(int lon, int n, int q) {
    vector<int> ans(n);
    vector<int> maxinum(n);
    for(int i=0;i<n;i++)maxinum[i]=lon-(n-i-1)*2; //maxima pos
    vector<int> mininum(n);
    for(int i=0;i<n;i++)mininum[i]=i*2;//minima pos
    ans[0]=guarda[0]=guarda[1]=0;
    int l=0,r;
    for(int i=1;i<n;i++){
    l=mininum[i-1];
    r=maxinum[i];
    int sol;//ultimo lugar en donde afecta el router anterior
    while(l<=r){
    	int mid=(l+r)/2,cerc;
    	if(guarda[mid]==-1) {
            guarda[mid]=use_detector(mid);
            for(int j=guarda[mid]+1;j<n;j++)
                mininum[j]=max(mid+(j-guarda[mid])*2,mininum[j]);
            for(int j=0;j<guarda[mid];j++)
                maxinum[j]=min(maxinum[j],mid+(j-guarda[mid])*2);
    	}
    	cerc=guarda[mid];
    	if(cerc<i){
    		l=mid+1;
    		sol=mid;
		}
		else r=mid-1;
	}
	ans[i]=2*sol-ans[i-1];
	}
	return ans;
}

Compilation message (stderr)

routers.cpp: In function 'std::vector<int> find_routers(int, int, int)':
routers.cpp:33:10: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |  ans[i]=2*sol-ans[i-1];
      |         ~^~~~

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