Submission #1200546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200546		Almonther	Finding Routers (IOI20_routers)	C++20	70.13 / 100	4 ms	1096 KiB

routers

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

#define ll long long
#define co cout<<
// stuff
// vector<int>points={0,2,6};
// ll use_detector(ll x){
//     ll mn=1e18,ans;
//     for(int i=0;i<points.size();i++){
//         ll dis=abs(x-points[i]);
//         if(dis<mn) mn=dis,ans=i;
//     }
//     return ans;
// }
std::vector<int> find_routers(int l, int n, int q){
    ll point=0,idx=0;
    ll ans[n+5]={};
    map<ll,ll>test;
    for(int i=0;i<n-1;i++){
        ll l=point,r=1e5;
        while(l<r){
            ll mid=(l+r+1)/2;
            test[mid]=use_detector(mid);
            if(test[mid]!=idx) r=mid-1;
            else l=mid;
        }
        point=(l-point)*2+point,idx=test[l+1];
        ans[idx]=point;
    }
    vector<int>v;
    for(int i=0;i<n;i++) v.push_back(ans[i]);
    return v;
}
// int main(){
//     vector<int>v=find_routers(6, 3, 10);
//     for(auto i:v) co i<<' ';
// }

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