Submission #623720

#	Time	Username	Problem	Language	Result	Execution time	Memory
623720		jophyyjh	Finding Routers (IOI20_routers)	C++14	100 / 100	5 ms	980 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:  n/x * log(x), x = 69  (~7500 steps, for [S4], but with caching)
 * Implementation 1.6
*/

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

typedef std::vector<int>  vec;

const int X = 69;


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();
    if (l == 100000 && n == 1000 && q == 20000) {
        vec init_pt = {0}, init_ask = {0};
        for (int i = X; i < l; i += X) {
            init_pt.push_back(i);
            init_ask.push_back(wrap_use(i));
        }
        init_pt.push_back(l);
        init_ask.push_back(n - 1);
        int m = init_pt.size();
        vec midpoints;
        for (int i = 0; i < m - 1; i++) {
            int a = init_pt[i], b = init_pt[i + 1];
            int left = init_ask[i], right = init_ask[i + 1];
            while (left < right) {
                int j1 = a, j2 = b;
                while (j1 < j2) {
                    int mid = (j1 + j2 + 1) / 2;
                    if (wrap_use(mid) == left)
                        j1 = mid;
                    else
                        j2 = mid - 1;
                }
                midpoints.push_back(j1);
                a = j1 + 1, left++;
            }
        }
        vec ans = {0};
        for (int mi : midpoints)
            ans.push_back(2 * mi - ans.back());
        return ans;
    } else {
        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: 40 / 40