Submission #1200441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200441		Warinchai	Finding Routers (IOI20_routers)	C++20	100 / 100	2 ms	1096 KiB

routers

#include "routers.h"
#include<bits/stdc++.h>
using namespace std;

int N,L;

int qr[1000005];

int Use_detector(int x){
    //cerr<<x<<"\n";
    if(x>=L)return N-1;
    if(qr[x]!=-1)return qr[x];
    return qr[x]=use_detector(x);
}

int sz=100;

int lg[100005];

std::vector<int> find_routers(int l, int n, int q) {
    for(int i=0;i<=1e5;i++)qr[i]=-1;
    lg[1]=0;
    for(int i=2;i<=1e5;i++)lg[i]=lg[i/2]+1;
    N=n;
    L=l;
    int id = 0;
    vector<int> ans;
    ans.push_back(0);
    int prv=0;
    sz=lg[l/n];
    sz=(1<<sz);
    for(int i=1;i<n;i++){
        int mx=sz;
        for(;Use_detector(prv+mx)==i-1;mx+=sz);
        int dis=0;
        //cerr<<mx<<"\n";
        for(int j=lg[mx];j>=0;j--){
            if(Use_detector(prv+dis+(1<<j))==i-1)dis+=(1<<j);
        }
        prv=prv+dis*2;
        //cerr<<prv<<"\n";
        ans.push_back(prv);
    }
	return ans;
}

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