Submission #1200495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200495		eyadooz	Finding Routers (IOI20_routers)	C++20	100 / 100	1 ms	584 KiB

routers

#include"routers.h"
// #include<bits/stdc++.h>
#include<vector>
using namespace std;
// int use_detector(int x) 
// {
//     cout << x << endl;
//     int y;
//     cin >> y;
//     return y;
// }
std::vector<int> find_routers(int k, int n, int q)
{
    vector<int> ans;
    ans.push_back(0);
    int asked[k+5];
    for(int i = 0;i <= k;i++) asked[i] = -1;
    for(int i = 1;i<n;i++) 
    {
        int l=0,r=k;
        while(l<r)
        {
            int mid = (l+r)/2;
            int x = 0;

            if(asked[mid] != -1) x = asked[mid];
            else x = use_detector(mid);
            asked[mid] = x;
            if(x<i) l=mid+1;
            else r=mid;
        }
        
        ans.push_back(((l-1)-ans.back())*2+ans.back());
    }

    return ans;
}

// int main()
// {
//     vector<int> a= find_routers(6, 3, 10000);
//     for(auto i : a) cout << i << " ";
// }

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