Submission #1202701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202701		ASGA_RedSea	Finding Routers (IOI20_routers)	C++20	98.93 / 100	2 ms	1608 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;


struct sgt{
    vector<int>s;
    int sz,lg;
    void init(int n){
        lg=__lg(n)+1;
        sz=1<<lg;
        s.assign(sz*2,0);
    }

    void edit(int i,int v){
        i+=sz;
        s[i]=v;
        while(i>1){
            i>>=1;
            s[i]=max(s[i*2],s[i*2+1]);
        }
    }
    int get(int v){
        if(s[1]<=v)return sz;
        int i=1;
        while(i<sz){
            if(s[i*2]>v)i*=2;
            else i=i*2+1;
        }

        return i-sz-1;
    }
};

sgt s;

vector<int>v;

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

mt19937 G;
int rnd(int l,int r){return G()%(r-l+1)+r;}

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

    G.seed(988244353);

    s.init(_l+1);

    if(Q==2e4)for(int i=rnd(2,300);i<=_l;i+=rnd(300,350))ask(i);

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

        if(i+1<n){
            int l=cur+1,r=min(_l,s.get(i)),m;
            while(l<=r){
                m=(l+r)/2;
                if(ask(m)>i)r=m-1;
                else l=m+1;
            }
            cur=l;
        }
    }

    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: 38.9312 / 40