Submission #810758

#	Time	Username	Problem	Language	Result	Execution time	Memory
810758		wortelworm	Finding Routers (IOI20_routers)	C++17	0 / 100	1 ms	300 KiB

routers

// #include "grader.cpp"

#include "routers.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> find_routers(int length, int n, int _q) {
    vector<int> answers(n);
    // go to closest (lower_eq) even number
    int global_upper = length & (~1);

    for (int i = 1; i < n; i++)
    {
        // find router i
        int minimum = answers[i - 1];

        // even, exclusive
        int lower = minimum;

        // even, inclusive
        int upper = global_upper;
        while (lower + 2 < upper) {
            int middle = (lower + upper) / 2;
            if (middle % 2 == 1) {
                middle --;
            }
            int test = lower + (middle - lower) / 2 + 1;
            int result = use_detector(test);
            if (result < i) {
                // the number is > middle
                lower = middle;
            } else {
                // the number is <= middle
                upper = middle;
            }
        }

        answers[i] = lower + 2;
    }
    
    return answers;
}

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