Znzryb's Blog

CF-1020-F. Goblin

Posted on 2025-04-26 Edited on 2026-02-16

思路讲解

终于是看懂题目是什么意思了。其实就是问你这张生成网格中的0的联通块最多包含多少个0。

比如这张图中是包含9个。

那么唯一的问题就是，这张生成网格太大了，最多可能有4e10个块。这就有点恐怖了。

如果说跑dfs，bfs， $O(n^2)$ 无法通过此题。

唉，其实像这种题反而难想，因为暴力太容易想到，但是暴力的优化就不是很容易了，可能要另起炉灶了。

那么就直接使用dp的类似思路，一列一列的推过去，然后就做出来了？一次AC！

推的代码

// 终于是看懂题目是什么意思了。其实就是问你这张生成网格中的0的联通块最多包含多少个0。
if(S[1]=='0') Cnt[1][0]=0,Cnt[1][1]=N-1;
else Cnt[1][0]=1;
FOR(i,2,N){
	if(S[i]=='0'){
		Cnt[i][0]=i-1;
		Cnt[i][1]=N-i;
		if(S[i-1]=='1'){ // 10情况，上半部分相连
			Cnt[i][0]+=Cnt[i-1][0];
		}else{      // 00 情况，上半部分和上半部分连，下半部分和下半部分连
			Cnt[i][0]+=Cnt[i-1][0];
			Cnt[i][1]+=Cnt[i-1][1];
		}
	}else{
		Cnt[i][0]=1;
		if(S[i-1]=='0'){ // 01情况，和下半部分连
			// 就是一列分为上下（如果是0）的话
			Cnt[i][0]+=Cnt[i-1][1];	// 和下面联通
		}
		// 如果是1直接就不联通了，开摆
	}
}

AC代码

源代码

// Problem: F. Goblin
// Contest: Codeforces - Codeforces Round 1020 (Div. 3)
// URL: https://codeforces.com/contest/2106/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T;
char S[MAXN];
ll Cnt[MAXN][3];

inline void solve(){
	cin>>N;
	FOR(i,0,N+5) Cnt[i][0]=0,Cnt[i][1]=0;
	FOR(i,1,N){
		cin>>S[i];
	}
	// 终于是看懂题目是什么意思了。其实就是问你这张生成网格中的0的联通块最多包含多少个0。
	if(S[1]=='0') Cnt[1][0]=0,Cnt[1][1]=N-1;
	else Cnt[1][0]=1;
	FOR(i,2,N){
		if(S[i]=='0'){
			Cnt[i][0]=i-1;
			Cnt[i][1]=N-i;
			if(S[i-1]=='1'){
				Cnt[i][0]+=Cnt[i-1][0];
			}else{
				Cnt[i][0]+=Cnt[i-1][0];
				Cnt[i][1]+=Cnt[i-1][1];
			}
		}else{
			Cnt[i][0]=1;
			if(S[i-1]=='0'){
				// 就是一列分为上下（如果是0）的话
				Cnt[i][0]+=Cnt[i-1][1];	// 和下面联通
			}
			// 如果是1直接就不联通了，开摆
		}
	}
	ll ans=0;
	FOR(i,1,N){
		ans=max({Cnt[i][1],ans,Cnt[i][0]});
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2106/submission/317269384
*/

心路历程（WA，TLE，MLE……）

CF-1020-E. Wolf

Posted on 2025-04-25 Edited on 2026-02-16

思路讲解

一般难度，看着比较唬人。

其实就是看看有多少个需要替换位置，需要将其替换为比k小或者大的数。

那其实我们只要知道有几个替换位置就行。因为这个替换无视距离，不要求连续。（读题不要读成以为是连续的了）
然后注意大的数和小的数是可以对冲的，能内部解决就内部解决，否则会WA testcase2 的第3104个点。

1 2	// 这些数肯定要换，但可以内部对冲的，就内部对冲，不能内部对冲的，就找外援(max-min) cout<<needRep+needRep_+(max(needRep_,needRep)-min(needRep,needRep_))<<" ";

AC代码

源代码

// Problem: E. Wolf
// Contest: Codeforces - Codeforces Round 1020 (Div. 3)
// URL: https://codeforces.com/contest/2106/problem/E
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,Q,T,P[MAXN];
ll Pos[MAXN];
ll sufP[MAXN];
// arr query[MAXN];

// ll needRep=0;

inline void solve(){
	cin>>N>>Q;
	FOR(i,0,N+5) {sufP[i]=0;}
	FOR(i,1,N){
		cin>>P[i];
		Pos[P[i]]=i;
	}
	// ROF(i,N,1){
		// sufP[i]=
	// }
	
	// m=l+r>>1
	// 他选择的排序是不能包含原数的(Pi_j!=k)
	// reoreder as he like
	// 找到一个需要替换位置，需要将其替换为比k小或者大的数
	// 那其实我们只要知道有几个替换位置就行
	FOR(i,1,Q){
		ll l,r,k;
		cin>>l>>r>>k;
		// query[i]={l,r,k,};
		if(Pos[k]>r || Pos[k]<l){
			cout<<"-1 ";
			continue;
		}
		ll needRep_=0,needRep=0,useNum_=0,useNum=0;
		ll idx=l+r>>1;
		ll pk=Pos[k];
		ll l_=l,r_=r;
		while(idx!=pk){
// #ifdef LOCAL
    // cerr<<"idx:"<< idx<<" pk:"<<pk<<" l_:"<<l_<<" r_:"<<r_ << '\n';
// #endif
			// if(r_<l_){
				// cout<<"-1 ";
				// break;
			// }
			if(idx<pk){
				// 需要向后跳
				if(P[idx]>k) ++needRep_;
				else ++useNum_;	// 也算是用掉了一个
				l_=idx+1;
				idx=(l_+r_)/2;
			}else{
				// 需要向前跳
				if(P[idx]<k) ++needRep;
				else ++useNum;
				r_=idx-1;
				idx=(r_+l_)/2;
			}
		}
		// if(r_<l_) continue;
		if(needRep==0 && needRep_==0) {cout<<"0 ";continue;}
		if(N-k-useNum<needRep){
			cout<<"-1 ";
			continue;
		}
		if(k-1-useNum_<needRep_){
			cout<<"-1 ";
			continue;
		}
		// 	这些数肯定要换，但可以内部对冲的，就内部对冲，不能内部对冲的，就找外援(max-min)
		cout<<needRep+needRep_+(max(needRep_,needRep)-min(needRep,needRep_))<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2106/submission/317259599
*/

心路历程（WA，TLE，MLE……）

写成这样

1 2	l_=idx+1; idx=(l_+r_)/2;

而不是这样

1 2	idx=(idx+1+r_)/2; l_=idx+1;

（l_的idx已经不是原来的idx了）

这种idx最好还是用固定式子得出

CF-1020-D. Flower Boy

Posted on 2025-04-25 Edited on 2026-02-16

思路讲解

preA配合sufA，寻找最优插值位置

AC代码

源代码

// Problem: D. Flower Boy
// Contest: Codeforces - Codeforces Round 1020 (Div. 3)
// URL: https://codeforces.com/contest/2106/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T,A[MAXN],B[MAXN],sufA[MAXN],preA[MAXN];

inline void solve(){
	cin>>N>>M;
	FOR(i,0,N+5){
		sufA[i]=0;
		preA[i]=0;
	}
	FOR(i,1,N){
		cin>>A[i];
	}
	deque<ll> q;
	FOR(i,1,M){
		cin>>B[i];
		q.pb(B[i]);
	}
	ll idx=0;
	FOR(i,1,N){
		if(q.empty()) break;
		if(A[i]>=q.front()) q.pop_front(),++idx;
		preA[i]=idx;
	}
	if(q.empty()){
		cout<<0<<"\n";
		return;
	}
	q.clear();
	FOR(i,1,M){
		q.pb(B[i]);
	}
	idx=0;
	ROF(i,N,1){
		if(A[i]>=q.back()){
			q.pop_back();
			++idx;
		}
		sufA[i]=idx;
	}
	
#ifdef LOCAL
    FOR(i,1,N){
    	cerr<<sufA[i]<<" ";
    }
    cerr<<"\n";
    FOR(i,1,N){
    	cerr<<preA[i]<<" ";
    }
    cerr<<"\n\n";
#endif

	ll ans=INF;
	bool haveAns=false;
	FOR(i,0,N){
		if(sufA[i+1]+preA[i]==M-1){
			ans=min(ans,B[preA[i]+1]);
			haveAns=true;
		}
	}
	if(!haveAns){
		cout<<-1<<"\n";
		return;
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
1
4 4
1 1 3 3
1 2 3 6
AC https://codeforces.com/contest/2106/submission/317145066
*/

心路历程（WA，TLE，MLE……）

CF-1013-E1. Canteen (Easy Version)

Posted on 2025-04-21 Edited on 2026-02-16

思路讲解

其实也是自己琢磨琢磨出来的，当然不好好写复盘大抵是看不懂以前自己的思路的。

FOR(i,0,N-1){
	diff[i]=B[i]-A[i];
}
ll ans=1;
// diff是负值表示需要调和

就是直接模拟肯定TLE，但是可以退而求其次，**一个一个模拟。**在这个需调和块遇到其他的需调和块之前，不用担心操作有后效性。在碰到其他调和块之后，让他先开路，如果他变成0了，再变成你了。

当然可能碰到多个调和块，这个时候就是使用栈来维护，一个为0弹出1个，换后面一个，直到处理完这个最初的，弹出。

AC代码

https://codeforces.com/contest/2089/submission/316959785

源代码

// Problem: E1. Canteen (Easy Version)
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/E1
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
// constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,K,T,A[MAXN],B[MAXN];
ll diff[MAXN];

inline ll mod(ll x){
	ll res=(x-1)%N;
	if(res<0) res+=N;
	return res;
}

inline void solve(){
	cin>>N>>K;
	// 0-based
	bool all0=true;
	for(int i=0;i<N;++i){
		cin>>A[i];
		if(A[i]!=0) all0=false;
	}
	if(all0){
		cout<<0<<"\n";
		return;
	} 
	FOR(i,0,N-1){
		cin>>B[i];
	}
	FOR(i,0,N-1){
		diff[i]=B[i]-A[i];
	}
	ll ans=1;
	// diff是负值表示需要调和
	FOR(i,0,N-1){
		if(diff[i]>=0) continue;
		ll idx=i;
		ll cnt=1;
		vector<ll> labs;
		labs.pb(i);
		while(diff[i]<0){
			++idx;
			++cnt;
			idx%=N;
			if(idx<0) idx+=N;
			
			if(diff[idx]>=0){
				// 现在需要处理的最后一个labs
				assert(!labs.empty());	// 保险一下，断言这个东西不为空，我RE也知道哪里RE
				ll lab=labs.back();
				diff[lab]+=diff[idx];
				diff[idx]=0;
				if(diff[lab]>0){
					// 这个情况其实是diff[idx]>=0的情况
					// 就是没减干净，所以说idx也要停一下，cnt也要停一下
					diff[idx]+=diff[lab];
					diff[lab]=0;
					if(lab!=i) --cnt;
					// lab=upLab;
					--idx;
					labs.pop_back();  // 起到lab=upLab的作用
					//--ltot;	// 起到lab=upLab的作用
					// if(ltot<0) break;
				} 
				// if(lab==i) ++cnt;
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}else{
				labs.pb(idx);
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}
		}
		ans=max(ans,cnt);
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2089/submission/316959785

*/

心路历程（WA，TLE，MLE……）

这段代码会造成这个死循环，虽然说比较隐蔽，但这个死循环的罪魁祸首就是upLab。

这个upLab和lab如果相同的会导致lab=upLab 这句话出现问题，并不起到作用。

死循环代码

		ll idx=i;
		ll lab=i;
		ll cnt=1;
		// vector<ll> labs;
		ll upLab=-1;
		while(diff[i]<0){
			++idx;
			++cnt;
			idx%=N;
			if(idx<0) idx+=N;
			
			if(diff[idx]>=0){
				diff[lab]+=diff[idx];
				diff[idx]=0;
				if(diff[lab]>0){
					diff[idx]+=diff[lab];
					diff[lab]=0;
					if(lab!=i) --cnt;
					lab=upLab;
					--idx;
				} 
				// if(lab==i) ++cnt;
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}else{
				upLab=lab;
				lab=idx;
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}
		}

这个代码过了5个点，但还是有点问题，怀疑是因为我这个算法没有去真实的记录每个点的实际抵消所需操作数，现在看起来要改一改了，确保这个每个点的抵消所需操作数都被真实记录。

但好像也不太对，就是我们都是把这个碰到的 $diff<0$ 的点搞到 $≥0$ 才罢休，而且这个也会记录到最初的点当中

https://codeforces.com/contest/2089/submission/316947463

错误代码

// Problem: E1. Canteen (Easy Version)
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/E1
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
// constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,K,T,A[MAXN],B[MAXN];
ll diff[MAXN];

inline ll mod(ll x){
	ll res=(x-1)%N;
	if(res<0) res+=N;
	return res;
}

inline void solve(){
	cin>>N>>K;
	// 0-based
	bool all0=true;
	for(int i=0;i<N;++i){
		cin>>A[i];
		if(A[i]!=0) all0=false;
	}
	if(all0){
		cout<<0<<"\n";
		return;
	} 
	FOR(i,0,N-1){
		cin>>B[i];
	}
	FOR(i,0,N-1){
		diff[i]=B[i]-A[i];
	}
	ll ans=1;
	// diff是负值表示需要调和
	FOR(i,0,N-1){
		if(diff[i]>=0) continue;
		ll idx=i;
		ll ltot=0;
		ll cnt=1;
		vector<ll> labs;
		labs.pb(i);
		while(diff[i]<0){
			++idx;
			++cnt;
			idx%=N;
			if(idx<0) idx+=N;
			
			if(diff[idx]>=0){
				ll lab=labs[ltot];
				diff[lab]+=diff[idx];
				diff[idx]=0;
				if(diff[lab]>0){
					diff[idx]+=diff[lab];
					diff[lab]=0;
					if(lab!=i) --cnt;
					// lab=upLab;
					--idx;
					--ltot;	// 起到lab=upLab的作用
					if(ltot<0) break;
				} 
				// if(lab==i) ++cnt;
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}else{
				// lab=idx;
				++ltot;
				labs.pb(idx);
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}
		}
		ans=max(ans,cnt);
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*


*/

事实证明我的猜想是对的，只是ltot这个东西就有问题，直接改成栈，把这个ltot优化掉了就好了

CF-1013-D. Simple Permutation

Posted on 2025-04-20 Edited on 2026-02-16

思路讲解

其实想明白了就很简单，就是这个就是平均数（向上取整），那么就找离平均数最近的素数就行，然后让这个数列的上界平均数不断是这个素数就行。

AC代码

源代码

// Problem: D. Simple Permutation
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T;
bool isPrime[MAXN];
vector<ll> primes;
set<ll> perm;
bool inAns[MAXN];

inline ll ceilDiv(ll x,ll cnt){
	return ceil(x*1.0l/cnt);
}

inline void genPrime(){
	for(int i=2;i<=MAXN-5;++i){
		isPrime[i]=true;
	}
	for(int i=2;i*i<=MAXN-5;++i){
		if(isPrime[i]){
			for(int j=2*i;j<=MAXN-5;j+=i){
				isPrime[j]=false;
			}
		}
	}
	for(int i=2;i<=MAXN-5;++i){
		if(isPrime[i]) primes.pb(i);
	}
}

inline void solve(){
	cin>>N;
	vector<ll> ans;
	perm.clear();
	for(int i=1;i<=N;++i){
		perm.insert(i);
		inAns[i]=false;
	}
	ll cnt=1,sum=0;
	
	// for(int i=SZ(primes)-1;i>=0;--i){
		// if(SZ(ans)>=N/3-1) break;
		// ll curP=primes[i];
		// while(true){
			// if(SZ(ans)>=N/3-1) break;
			// ll l=(curP-1)*cnt-sum;	// 其实是下界
// // #ifdef LOCAL
    // // cerr << l << '\n';
// // #endif
			// auto it=perm.lower_bound(l+1);
			// if(it==perm.end()) break;
			// ll num=*it;
			// if(ceilDiv(num+sum,cnt)==curP){
				// ans.pb(num);
				// ++cnt;
				// sum+=num;
				// inAns[num]=true;
				// perm.erase(it);
			// }else{
				// break;
			// }
		// }
	// }
	
	ll curP=*lower_bound(all(primes),N/2);
	while(true){
		// if(SZ(ans)>=N/3-1) break;
		ll l=(curP-1)*cnt-sum;	// 其实是下界
// #ifdef LOCAL
// cerr << l << '\n';
// #endif
		auto it=perm.lower_bound(l+1);
		if(it==perm.end()) break;
		ll num=*it;
		if(ceilDiv(num+sum,cnt)==curP){
			ans.pb(num);
			++cnt;
			sum+=num;
			inAns[num]=true;
			perm.erase(it);
		}else{
			break;
		}
	}
// #ifdef LOCAL
    // cerr << ans.size() << '\n';
// #endif
	for(int i=0;i<ans.size();++i){
		cout<<ans[i]<<" ";
	}
	for(int i=1;i<=N;++i){
		if(!inAns[i]) cout<<i<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	genPrime();
// #ifdef LOCAL
    // for(int i=0;i<primes.size();++i){
    	// cerr<<primes[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
WA https://codeforces.com/contest/2090/submission/316398539
AC https://codeforces.com/contest/2090/submission/316487010
*/

心路历程（WA，TLE，MLE……）

https://codeforces.com/contest/2090/submission/316398539

其实还可以，过了8个点，但是在面对大数的情况时力不从心。

错误代码1

// Problem: D. Simple Permutation
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T;
bool isPrime[MAXN];
vector<ll> primes;
set<ll> perm;
bool inAns[MAXN];

inline ll ceilDiv(ll x,ll cnt){
	return ceil(x*1.0l/cnt);
}

inline void genPrime(){
	for(int i=2;i<=MAXN-5;++i){
		isPrime[i]=true;
	}
	for(int i=2;i*i<=MAXN-5;++i){
		if(isPrime[i]){
			for(int j=2*i;j<=MAXN-5;j+=i){
				isPrime[j]=false;
			}
		}
	}
	for(int i=2;i<=MAXN-5;++i){
		if(isPrime[i]) primes.pb(i);
	}
}
// inline ll bsearch(ll sum,ll cnt){
	// ll l=1,r=mod;
	// while(l<r){
		// ll mid=l+r+1>>1;
		// if(ceilDiv(mid,sum,cnt)<=3){
			// l=mid;
		// }else{
			// r=mid-1;
		// }
	// }
	// return l;
// }

inline void solve(){
	cin>>N;
	vector<ll> ans;
	perm.clear();
	for(int i=1;i<=N;++i){
		perm.insert(i);
		inAns[i]=false;
	}
	ll cnt=1,sum=0;
	for(int i=0;i<primes.size();++i){
		if(ans.size()>=N) break;
		ll curP=primes[i];
		while(true){
			if(ans.size()>=N) break;
			ll l=(curP-1)*cnt-sum;	// 其实是下界
// #ifdef LOCAL
    // cerr << l << '\n';
// #endif
			auto it=perm.lower_bound(l+1);
			if(it==perm.end()) break;
			ll num=*it;
			if(ceilDiv(num+sum,cnt)==curP){
				ans.pb(num);
				++cnt;
				sum+=num;
				inAns[num]=true;
				perm.erase(it);
			}else{
				break;
			}
		}
	}
#ifdef LOCAL
    cerr << ans.size() << '\n';
#endif
	for(int i=0;i<ans.size();++i){
		cout<<ans[i]<<" ";
	}
	for(int i=1;i<=N;++i){
		if(!inAns[i]) cout<<i<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	genPrime();
// #ifdef LOCAL
    // for(int i=0;i<primes.size();++i){
    	// cerr<<primes[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/