제출 #1203684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203684		maya_s	Finding Routers (IOI20_routers)	C++20	69.65 / 100	1 ms	328 KiB

routers

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

static int l, n, q;
static std::vector<int> p;
static std::vector<int> answer;
static int queries = 0;

// int use_detector(int x)
// {
// 	queries++;
//     assert(x >= 0 && x <= l);
//     std::vector<int>::iterator left, right;
//     right = std::upper_bound(p.begin(), p.end(), x);
//     left = std::prev(right);

//     if (right == p.end()) {
//         return n - 1;
//     } else if ((x - *left) <= (*right - x)){
//         return std::distance(p.begin(), left);
//     } else {
//         return std::distance(p.begin(), right);
//     }
// }

std::vector<int> find_routers(int L, int N, int Q) {
    ll last = 0;
    vector<ll> ans = {0};
    ll power = 1;
    while(power < L) power *= 2;
    for(ll lable = 1; lable < N; lable++){
        ll loc = last, add = power;
        while(loc + add > L) add /= 2;
        while(add){
            ll x = use_detector(loc+add);
            if(x < lable) loc += add;
            add /= 2;
        }
        ans.push_back(last + 2*(loc-last));
        last += 2*(loc-last);
    }
    return ans;
}

// int main()
// {
//     assert(scanf("%d %d %d", &l, &n, &q) == 3);
//     p.resize(n);
//     for (int i = 0; i < n; i++) {
//         assert(scanf("%d", &p[i]) == 1);
//         if (i) {
//             assert(p[i-1] < p[i]);
//         }
//     }

//     fclose(stdin);

//     answer = find_routers(l, n, q);

//     assert((int) answer.size() == n);
//     for (int i = 0; i < n; i++)
//     {
//         assert(answer[i] >= 0 && answer[i] <= l && answer[i] % 2 == 0);
//     }

//     for (int i = 0; i < n; i++)
//     {
//         if (i) printf(" ");
//         printf("%d", answer[i]);
//     }
//     printf("\n");

//     printf("%d\n", queries);
// }

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