Submission #439427

#	Time	Username	Problem	Language	Result	Execution time	Memory
439427		Tc14	Finding Routers (IOI20_routers)	C++17	65.68 / 100	2 ms	296 KiB

routers

#include <bits/stdc++.h>
#include "routers.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;

int L;

int use(int x) {
    if (x > L) return INF;
    else return use_detector(x);
}

ve<int> find_routers(int l, int n, int q) {

    ve<int> Ans(n);
    L = l;

    int p = 0;
    for (int i = 1; i < n; i++) {

        int x = 2;
        while (use(p + x) == i - 1) {
            x <<= 1;
        }

        int a = p + x;
        x >>= 1;
        while (x != 0) {
            if (use(a - x) != i - 1) {
                a -= x;
            }
            x >>= 1;
        }

        p = p + 2 * (a - p - 1);
        Ans[i] = p;
    }

    return Ans;
}

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