Submission #1200555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200555		Almonther	Finding Routers (IOI20_routers)	C++20	39 / 100	5 ms	840 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;
    map<ll,ll>mp;
    for(int i=0;i<n-1;i++){
        ll mx=0;
        for(auto j:mp) mx=max(mx,j.second);
        ll l=mp[idx]+1,r=mx-1;
        if(r<l) r=1e5;
        ll cnt=0;
        while(l<r){
            ll mid=(l+r+1)/2;
            if(test[mid]==0) test[mid]=use_detector(mid)+1,cnt++;
            mp[test[mid]]=max(mp[test[mid]],mid);
            if(test[mid]-1!=idx) r=mid-1;
            else l=mid;
        }
        if(cnt>=20) return {-1};
        point=(l-point)*2+point,idx=test[l+1]-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: 0 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 40