Submission #794031

#	Time	Username	Problem	Language	Result	Execution time	Memory
794031		ln_e	Finding Routers (IOI20_routers)	C++17	100 / 100	2 ms	1152 KiB

routers

    #include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
    #include "routers.h"
    using ll=long long;
    using ld=long double;
    int const INF=1000000005;
    ll const LINF=1000000000000000005;
    ll const mod=6700417;
    ld const PI=3.14159265359;
    ll const MAX_N=3e5+5;
    ld const EPS=0.00000001;
    #pragma GCC optimize("O3")
    #pragma GCC optimize("Ofast")
    #define f first
    #define s second
    #define pb push_back
    #define mp make_pair
    #define endl '\n'
    #define sz(a) (int)a.size()
    #define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    using namespace std;
    ll viz[100005];
    ll check(ll pos,ll indx){
        if(viz[pos]!=0){
            if(viz[pos]-1>=indx){
                return 1;
            }else return 0;
        }
        int x=use_detector(pos);
        viz[pos]=x+1;
        if(x>=indx){
            return 1;
        }else return 0;
    }
    std::vector<int> find_routers(int st, int n, int q) {
        vector<int>ans;
        ans.pb(0);
        ll last=0;
        for(ll i=1;i<n;i++)
        {
            ll l=0,r=st,res=0;
            while(l<=r){
                ll mid=(l+r)/2;
                if(check(mid,i)){
                    res=mid;
                    r=mid-1;
                }else l=mid+1;
            }
            int pos=res+res-last-2;
            ans.pb(min(pos,st));
            last=pos;
        }
        return ans;
    }

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