Submission #559422

#	Time	Username	Problem	Language	Result	Execution time	Memory
559422		AlperenT	Finding Routers (IOI20_routers)	C++17	99.46 / 100	6 ms	332 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

vector<int> find_routers(int len, int n, int q) {
    vector<int> ans;

    vector<int> seen(n + 5, INF);

    ans.push_back(0);

    int lft = 0;

    for(int cur = 1; cur < n; cur++){
    	again:

    	int curlen = ceil(((len - lft) / (n - cur)) * 0.98);

    	int l = lft, r = min(lft + curlen, len) + 1;

    	if(seen[cur] != INF) r = seen[cur] + 1;

    	while(r - l > 1){
    		int m = l + (r - l) / 2;

    		int x = use_detector(m);

    		seen[x] = min(seen[x], m);

    		if(x >= cur) r = m;
    		else l = m;
    	}

    	if(r == min(lft + curlen, len) + 1){
    		lft = r - 1;
    		goto again;
    	}

    	l = r - 1;

    	lft = l + (l - ans.back());

    	ans.push_back(lft);
    }

    return ans;
}

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