Submission #400988

#	Time	Username	Problem	Language	Result	Execution time	Memory
400988		jairRS	Finding Routers (IOI20_routers)	C++17	39 / 100	2 ms	592 KiB

routers

#include "routers.h"
#define pb push_back
using namespace std;

std::vector<int> find_routers(int l, int n, int q) {
  vector<int> ans = {0};
	vector<int> firstSeen(n + 1, l);
	vector<int> lastSeen(n + 1, 0);
	vector<int> memo(l + 1, -1);
	firstSeen[0] = 0;
	lastSeen[0] = 1;

	int lastRouterIndex = 0;
	for (int toFind = 1; toFind <= n - 1; toFind++)
	{
		int lo = lastSeen[toFind - 1] + 1, hi = firstSeen[toFind + 1];
		while(lo <= hi){
			int mid = (lo + hi)/2;
			int detected = (memo[mid] != -1 ? memo[mid] : use_detector(mid));
			memo[mid] = detected;
			if(detected >= toFind) hi = mid - 1;
			else lo = mid + 1;

			firstSeen[detected] = min(firstSeen[detected], mid);
			lastSeen[detected] = max(lastSeen[detected], mid);
		}

		int nextRouter = lastRouterIndex + (lo - 1 - lastRouterIndex)*2;
		ans.pb(nextRouter);
		lastSeen[toFind] = max(lastSeen[toFind], nextRouter + 1);
	}

	return ans;
}

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