oj.uz

Submission #810758

# Submission time Handle Problem Language Result Execution time Memory
810758 2023-08-06T15:00:06 Z wortelworm Finding Routers (IOI20_routers) C++17
0 / 100
 1 ms 300 KB 
// #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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Incorrect location of routers
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Incorrect location of routers
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Incorrect location of routers
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Incorrect location of routers
2 Halted 0 ms 0 KB -