Submission #433238

#	Time	Username	Problem	Language	Result	Execution time	Memory
433238		amunduzbaev	Finding Routers (IOI20_routers)	C++14	100 / 100	1 ms	204 KiB

routers

#include "routers.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include "bits/stdc++.h"
using namespace std;

template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }

const int N = 1e3+5;
int tt[N];

void fun(int l, int r, int a, int b){
	if(l >= r || a + 1 >= b) return;
	//~ cout<<l<<" "<<r<<" "<<a<<" "<<b<<endl;
	int m = (a + b)>>1;
	int t = use_detector(m);
	umax(tt[t], m);
	fun(l, t, a, m);
	fun(t, r, m, b);
}

/*
 
5 2 10
0 4
 
6 3 10
0 2 6
 
*/

vector<int> find_routers(int l, int n, int q) {
    fun(0, n-1, 0, l);
    vector<int> res(n, 0);
    for(int i=1;i<n;i++) res[i] = res[i-1] + (tt[i-1] - res[i-1]) * 2;
    return res;
}

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