제출 #810771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810771		wortelworm	Finding Routers (IOI20_routers)	C++17	76.05 / 100	2 ms	340 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 = minimum + (middle - minimum) / 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: 16 / 16
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 16.048000000000002 / 40