제출 #1224587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224587		ByeWorld	Finding Routers (IOI20_routers)	C++20	99.94 / 100	1131 ms	364316 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 = 1010;

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

int que(int mid){
	for(int i=1; i<=n-1; i++)
		if(MN[i] <= mid && mid <= MX[i]) return i;
	return us(mid); 
}
void find(int idx){
	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++;

	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;
	for(int i=1; i<=n-1; i++)
		if(dis[i]!=-1 && a[i]!=-1) a[i] = dis[i]-a[i-1];

	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=1; i<=n-1; i++){
		a[i] = -1; MN[i] = ma; MX[i] = -1; dis[i] = -1;
	}

	solve(1, n-1);
	// if(n/2 != 0){
	// 	find(n/2);
	// 	for(int i=n/2+1; i<=n-1; i++) find(i);
	// 	for(int i=n/2-1; i>=1; i--) find(i);
	// } else {
	// 	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: 39.936 / 40