Submission #1202693

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

routers

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "Ahmed Samed Gomaa"


#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

int use_detector(int x);

using namespace std;
using ll=long long;


vector<int>v;

int q;
int ask(int x){
    if(v[x]==-1){
        assert(q>0);
        q--;
        v[x]=use_detector(x);
    }
    return v[x];
}


vector<int>find_routers(int _l,int n,int Q){
    q=Q;
    v.assign(_l+1,-1);

    vector<int>ans;
    int cur=0;
    for(int i=0;i+1<n;i++){
        int l=0,r=_l,m;
        while(l<=r){
            m=(l+r)/2;
            if(ask(m)>i)r=m-1;
            else l=m+1;
        }

        if(i==0){
            ans.push_back(0);
        }
        else{
            int L=cur-1;
            ans.push_back(L-ans.back()+L);
        }

        if(i+1<n)cur=l;
    }
    cur--;
    ans.push_back(cur-ans.back()+cur);

    return ans;
}


//signed main(){
//    ios_base::sync_with_stdio(0);cin.tie(0);
//
//
//    ;
//
//
//    return 0;
//}

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