Submission #1201216

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

routers

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include "routers.h"
using namespace std;
 
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define ll long long
#define ld long double
#define ui uint64_t
#define cont(set, element) ((set).find(element) != (set).end())
 
/********* DEBUG *********/
 
template <typename T>
void outvec(const vector<T>& Z){
    for (const T& x : Z)
    cout << x << ' ';
    cout << "\n";
}
void printVariable(const any& var) {
    if (!var.has_value()) {
        cout << "null";
        return;
    }

    if (var.type() == typeid(int)) {
        cout << any_cast<int>(var);
    } else if (var.type() == typeid(double)) {
        cout << any_cast<double>(var);
    } else if (var.type() == typeid(float)) {
        cout << any_cast<float>(var);
    } else if (var.type() == typeid(char)) {
        cout << any_cast<char>(var);
    } else if (var.type() == typeid(bool)) {
        cout << (any_cast<bool>(var) ? "true" : "false");
    } else if (var.type() == typeid(string)) {
        cout << any_cast<string>(var);
    } else if (var.type() == typeid(const char*)) {
        cout << any_cast<const char*>(var);
    } else if (var.type() == typeid(long long)) {
        cout << any_cast<long long>(var);
    } else {
        cout << "[unknown type]";
    }
}

template<typename... Args>
void outval(Args... args) {
    vector<any> variables = {args...};
    
    for (size_t i = 0; i < variables.size(); ++i) {
        printVariable(variables[i]);
        if (i != variables.size() - 1) {
            cout << " ";
        }
    }
    cout << "\n";
}

#define nl "\n"
#define sp << " " <<

/********* DEBUG *********/

const ll MOD = 1000000007;
const ll inf = 1e18;
const ll mxN = 1000005;

vector<int> find_routers(int l, int n, int q) {
    //outval("got:",orig);
    vector<int> memo(l, -1);
    vector<int> ub(n, l);
    vector<int> ans;
    ans.push_back(0);

    memo[0] = 0;
    while (sz(ans) < n){
        int bk = ans[sz(ans)-1];
        int _l = bk, _r = ub[sz(ans)];

        while (_l <= _r){
            //outval("_l, _r:",_l,_r);
            int m = (_l+_r)/2;
            int near;
            
            if (memo[m] == -1)
                memo[m] = near = use_detector(m);
            else
                near = memo[m];

            ub[near] = min(ub[near], m);
            //outval("got:",near);
            
            if (near == sz(ans)-1)
                _l = m+1;
            else
                _r = m-1;
        }
        //outval("fin_l, _r:",_l,_r);
        
        int val = (_l - bk-1) * 2 + bk;
        ans.push_back(val);
    }

    //outvec(ans);
	return ans;
}

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