【集训DAY5】快速排序【模拟】【数学】

思路：

我们直接倒着来判断就行了

#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN = 50000;

int n, k;
int a[MAXN], ans[MAXN], id[MAXN];

int main() {
    
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= k; i ++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i ++) id[i] = i;
	int l = 1, r = n, wh = 1;
	for(int i = 1; i <= n; i ++) {
    
		int x = a[(i - 1) % k + 1] % (n - i + 1) + l;
		if(id[x] == wh) {
    
			ans[id[x]] = l;
			swap(id[x], id[l]);
			l ++;
			while(ans[wh]) wh ++;
		}
		else 
		{
    
			ans[id[x]] = r;
			swap(id[x], id[l]);
			swap(id[l], id[r]);
			r --;
		}
	}
	for(int i = 1; i <= n; i ++) printf("%d\n", ans[i]);
	return 0;
}