Submission #1224624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224624		ByeWorld	Finding Routers (IOI20_routers)	C++20	100 / 100	10 ms	10228 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
#define us use_detector
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;

void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
const int MAXN = 1e5+10;

int n, ma;
int a[1010], dis[1010]; // i ke i-1
set<int> le[MAXN], ri[MAXN];
int MN[MAXN], MX[MAXN], qu[MAXN];

int que(int mid){
	if(qu[mid] != -1) return qu[mid];
	for(int i=1; i<=n-1; i++)
		if(MN[i] <= mid && mid <= MX[i]) return qu[mid] = i;
	return qu[mid] = us(mid); 
}
void find(int idx){
	for(int i=1; i<=n-1; i++)
		if(dis[i]!=-1 && a[i]!=-1) a[i] = dis[i]-a[i-1];

	// int mx = 0, mn = ma+1;
	// for(int i=0; i<=idx-1; i++) chmx(mx, a[i]);
	// for(int i=idx+1; i<=n-1; i++) 
	// 	if(a[i] != -1) chmn(mn, a[i]);

	// int l=mx+1, r=mn-1, mid=0;
	// if(!le[idx].empty()) chmx(l, *--le[idx].end());
	// if(!ri[idx].empty()) chmn(r, *ri[idx].begin());
	// int cnt=l; l++;

	int l=0, r=ma, mid=0, cnt=-1;
	while(l<=r){
		mid = md;
		int ret = que(mid);
		// chmn(MN[ret], mid); chmx(MX[ret], mid);

 	// 	for(int i=1; i<=ret-1; i++) ri[i].insert(mid);
		// for(int i=ret+1; i<=n-1; i++) le[i].insert(mid);

		if(ret < idx) cnt = mid, l = mid+1;
		else r = mid-1;
	}
	dis[idx] = 2*cnt;
}

// void solve(int le, int ri){
// 	if(le>ri) return;

// 	// find(le);
// 	// solve(le+1, ri);
// 	int mid = (le+ri)>>1;
// 	find(mid);
// 	solve(le, mid-1); solve(mid+1, ri);
// }
std::vector<int> find_routers(int MA, int N, int q) {
	n = N; ma = MA;
	for(int i=0; i<=ma; i++) qu[i] = -1;
	for(int i=1; i<=n-1; i++){
		a[i] = -1; MN[i] = ma; MX[i] = -1; dis[i] = -1;
	}

	// if(n==1000){
	// 	solve(1, 512);
	// 	solve(513, 768);
	// 	// solve(1, 768);
	// 	solve(769, 999);
	// } else solve(1, n-1);
	for(int i=1; i<=n-1; i++) find(i);

	vector<int> ans; ans.pb(0);
	for(int i=1; i<=n-1; i++){
		a[i] = dis[i]-a[i-1];
		// cout << a[i] << " a\n";
		ans.pb(a[i]);
		assert(a[i] != -1);
	}
	// for(auto in : ans) cout << in << " in\n";
	return ans;
}

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