Submission #559432

#	Time	Username	Problem	Language	Result	Execution time	Memory
559432		AlperenT	Finding Routers (IOI20_routers)	C++17	100 / 100	2 ms	724 KiB

routers

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

using namespace std;

const int INF = 1e9;

vector<int> asked;

int ask(int x){
	if(asked[x] != INF) return asked[x];
	else return asked[x] = use_detector(x);
}

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

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

    asked.assign(len + 5, INF);

    ans.push_back(0);

    int lft = 0;

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

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

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

    	if(seen[cur] != INF) r = min(seen[cur], r);

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

    		int x = ask(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: 40 / 40