Submission #1203556

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

routers

#include <bits/stdc++.h>
using namespace std;
map<int, int> first;
vector<int> found;
#include "routers.h"

/*int use_detector(int x);*/

int findfromprevplace(int i, int x, int l){
    int start = x+1, end;
    if(first.empty()) end = l;
    else end = (*first.begin()).second-1;
    int lasti = x, curr, middle;
    while(start<=end){
        middle = (start+end)/2;

        if(found[middle] == -1) {
            curr = use_detector(middle);
            found[middle] = curr;
        }else {curr = found[middle];}

        if (first.find(curr) == first.end()) first[curr] = middle;
        else first[curr] = min(first[curr], middle);

        if(curr != i){
            end = middle -1;
        }else{
            lasti = max(lasti, middle);
            start = middle +1;
        }
    }
    if(first.find(i+1) != first.end()) first.erase(i+1);
    if(first.find(i)!=first.end()) first.erase(i);
    return 2*lasti-x;
}

std::vector<int> find_routers(int l, int n, int q){
    vector<int> ans;
    ans.push_back(0);
    int currfound = 0;
    int i = 0;
    found.resize(l+1, -1);
    while(ans.size()<n){
        currfound = findfromprevplace(i, currfound, l);
        ans.push_back(currfound);
        i++;
    }
    return ans;
}

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