Submission #1230342

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

routers

#include "routers.h"
#include <iostream>
using namespace std;

std::vector<int> find_routers(int l, int n, int q) {
    std::vector<int> ans(1),memo(l+10,-1);
    if(q==20000){
        int maks=l;
        for(int i=1;i<n;i++){
            int med=0;
            int l=ans.back()+1,r=maks;
            while(l<=r){
                int mid=(l+r)/2;
                int x;
                if(memo[mid]!=-1)memo[mid]=use_detector(mid);
                x=memo[mid];
                // cout<<i<<" "<<l<<" "<<r<<" "<<mid<<" "<<x<<endl;
                if(i<=x) r=mid-1;
                else{
                    if(x==i-1) med=mid; 
                    l=mid+1;
                }
            }
            ans.push_back(med*2-ans.back());
            // cout<<"ans "<<i<<" "<<med<<endl;
        }
        // cout<<ans.size()<<endl;
        // for(int i=0;i<n;i++) cout<<ans[i]<<" ";
        // cout<<endl;
    }
    else if(n==2){
        int maks=l;
        int l=1,r=maks;
        int med=0;
        while(l<=r){
            int mid=(l+r)/2;
            int x=use_detector(mid);
            if(x==1) r=mid-1;
            else{
                med=mid; 
                l=mid+1;
            }
        }
        ans.push_back(med*2);
    }
    else{
            int las=0;
            for(int i=1;i<=l;i++){
                int cur=use_detector(i);
                // cout<<cur<<" ";
                if(las != cur){
                    int mid=i-1;
                    int dis=2*mid-ans.back();
                    ans.push_back(dis);
                }
                las=cur;
            }
    }
	return ans;
}
// 0 4 6 8
// x       x   x   x
// 0 1 2 3 4 5 6 7 8 
// 1 1 1 2 2 2 3 3 4
   

// 0 4 8
// x       x       x
// 0 1 2 3 4 5 6 7 8 
// 1 1 1 2 2 2 2 4 4

// mid -> i
// mid+1 -> i+1
// mid (before change)

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