Educational Codeforces Round 131 (Div. 2)

CONTEST传送门

战况

Standing

Standing

Rating

补题

C - Schedule Management

错因

写二分的时候里面应该要用 $long long$ 存答案的，我用 $int$ 存了，没有注意到最大数据范围会不会超过 $int$ 的范围。

D - Permutation Restoration

题目大意

有一个排列 $a$ ，然后由排列 $a$ 经过操作 $b_i=\lfloor\frac{i}{a_i}\rfloor$ 得到数组 $b$ 。

输入数组 $b$ ，求出一个符合题意的排列 $a$ 。

思路

这道题很像之前写过的有一道区间问题的题目，每个位置上符合条件的数构成了一个区间，我们首先计算出每个位置上的区间的左右端点值，定义一个 $pair$ 的优先队列，规则是小的先出，具体思路为，根据左端点大小给每个区间排个序，左端点小的先入优先队列，入队的 $pair$ 值为 $[r[i],i]$ ，即这个点的右端点值和这个点的 $id$ ，之后根据这个顺序以此从 $1$ 到 $n$ 赋值即可，很像之前的一个区间处理的问题。

代码

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<iostream>
#include<unordered_set>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Inf 0x3f3f3f3f
//#define int long long
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef pair<P,int> PP;
const int MAXX=500005;
const double eps=0.0000001;
const LL mod=1000000007;

int n,s[MAXX],a[MAXX];
int l[MAXX],r[MAXX];
vector<int> pre[MAXX];
priority_queue<P,vector<P>,greater<P> > pq;

inline void solve_it(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&s[i]);
	for(int i=1;i<=n;++i){
		int ll=1,rr=n,mid;
		while(ll<rr){
			mid=(ll+rr)/2;
			if(mid==ll){
				if(i/mid!=s[i])
					ll=rr;
				break;
			}
			if(i/mid>s[i])
				ll=mid+1;
			else
				rr=mid;
		}
		l[i]=ll;
		rr=n;
		while(ll<rr){
			mid=(ll+rr)/2;
			if(mid==ll){
				if(i/rr==s[i])
					ll=rr;
				break;
			}
			if(i/mid>=s[i])
				ll=mid;
			else
				rr=mid-1;
		}
		r[i]=ll;
//		printf("*%d %d\n",l[i],r[i]);
	}
	
	for(int i=1;i<=n;++i)
		pre[i].clear();
	while(!pq.empty())
		pq.pop();
	
	for(int i=1;i<=n;++i)
		pre[l[i]].emplace_back(i);
	for(int i=1;i<=n;++i){
		for(int jj:pre[i])
			pq.emplace(P(r[jj],jj));
		a[pq.top().second]=i;
		pq.pop();
//		printf("*%d ",pq.size());
	}
//	printf("\n");
	for(int i=1;i<n;++i)
		printf("%d ",a[i]);
	printf("%d\n",a[n]);
}

signed main(){
	LL T;scanf("%lld",&T);
	while(T--)
		solve_it();
	
	return 0;
}