Submission #1201613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201613		hihihah	Finding Routers (IOI20_routers)	C++20	77 / 100	1 ms	328 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define all(x) x.begin(),x.end()
using namespace std;

vector <int> find_routers (int l, int n, int q) {
    int sq = 63;
    vector <int> pos;
    pos.push_back (0);
    pii mx = {0, 0};
    for (int i = 1; i < n; i ++) {
        int L = pos.back() + 1, R = l;
        int cnt = 0;
        if (mx.first >= i) {
            R = mx.second;
        }
        else {
            int v = 0;
            do {
                cnt ++;
                R = pos.back () + sq * cnt;
                if (R >= l) {
                    mx = {n, l};
                    break;
                }
            }
            while ((v = use_detector (pos.back () + sq * cnt)) == i - 1);
            if (mx.first < v) mx = {v, pos.back() + sq * cnt};
        }
        R = min (R, l - 1);

        int ans = 0;
        while (L <= R) {
            int mid = L + R >> 1;
            if (use_detector (mid) == i - 1) {
                ans = mid;
                L = mid + 1;
            }
            else R = mid - 1;
        }
        pos.push_back (pos.back() + (ans - pos.back()) * 2);
    }
    return pos;
}

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