Submission #623721

#	Time	Username	Problem	Language	Result	Execution time	Memory
623721		jophyyjh	Finding Routers (IOI20_routers)	C++14	96.34 / 100	6 ms	1116 KiB

routers

/**
 * Well, if we naively do binary search per router, the score is ~70. After that, I
 * was thinking if we can minimize the num. of queries by "re-using" information.
 * use_detector() is clearly an increasing function, so
 *              use_detector(l) = use_detector(r) 
 *        => use_detector(l) = use_detector(l+1) = ... = use_detector(r).
 * This means we can do some form of caching, though its efficiency is unknown. Also,
 * we do not know whether the grader is adaptive, but I'm pretty sure it can reduce
 * the num. of queries significantly.
 * 
 * Again, our task is to find the last point v with use_detector(v) = x (for each x).
 * First, check a point every x points, and call these checked points "initial pts".
 * Now, the "endpoints" we're finding must be between two initial points, so we can
 * do binary jump for each one of them. The num of steps is l/x + n * log_2(x). The
 * optimal x is 69, which yields at most 7557 steps (worst case). Good enough~
 * 
 * Steps needed:  ...
 * Implementation 0.9		(Just for testing my way of cache)
*/
 
#include <bits/stdc++.h>
#include "routers.h"

typedef std::vector<int>  vec;

 
std::map<int, int> cache1;
std::map<int, int, std::greater<int>> cache2;
 
int wrap_use(int i) {
    auto it1 = cache1.lower_bound(i);
    auto it2 = cache2.lower_bound(i);
    if (it1 != cache1.end() && it2 != cache2.end()) {
        if (it1->second == it2->second)
            return it1->second;
    }
    int result = use_detector(i);
    cache1[i] = cache2[i] = result;
    return result;
}
 
vec find_routers(int l, int n, int q) {
    cache1.clear();
    cache2.clear();
  	vec ans = {0};
  	for (int i = 0; i < n - 1; i++) {
    	int prev = ans.back();
    	int a = prev, b = l;
    	while (a < b) {
      	int mid = (a + b + 1) / 2;
      	if (wrap_use(mid) == i)
        	a = mid;
      	else
        	b = mid - 1;
    	}
    	ans.push_back(2 * a - prev);
  	}
  	return ans;
}

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