Submission #794009

#	Time	Username	Problem	Language	Result	Execution time	Memory
794009		ln_e	Finding Routers (IOI20_routers)	C++17	39 / 100	2 ms	2004 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]!=-1){
    		if(viz[pos]>=indx){
    			return 1;
    		}else return 0;
    	}
    	int x=use_detector(pos);
    	viz[pos]=x;
    	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=0;i<st;i++)
        {
            viz[i]=-1;
        }
        for(ll i=1;i<n;i++)
        {
        	ll l=last+1,r=st-2*(n-i-1),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: 0 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 40