提出 #46644175

ソースコード 拡げる

#include<iostream>
#include<atcoder/dsu>
using namespace std;
int N;
int P[2<<17],invP[2<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;cin>>T;
	for(;T--;)
	{
		cin>>N;
		atcoder::dsu uf(N);
		for(int i=0;i<N;i++)
		{
			cin>>P[i];
			invP[--P[i]]=i;
			uf.merge(i,P[i]);
		}
		int other=0;
		auto M=[&](int u,int v)
		{
			uf.merge(u,v);
			swap(P[u],P[v]);
			swap(invP[P[u]],invP[P[v]]);
		};
		for(int i=0;i<N;i++)
		{
			if(!uf.same(0,i))M(invP[i],i-1);
			while(other<N&&uf.same(other,0))other++;
			if(other<P[i])M(i,invP[other]);
		}
		for(int i=0;i<N;i++)cout<<P[i]+1<<(i+1==N?"\n":" ");
	}
}

提出情報

提出日時
問題 D - Good Permutation
ユーザ kotatsugame
言語 C++ 20 (gcc 12.2)
得点 700
コード長 630 Byte
結果 AC
実行時間 27 ms
メモリ 5588 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 700 / 700
結果
AC × 1
AC × 42
セット名 テストケース
Sample 01-sample-01.txt
All 01-sample-01.txt, 02-min-01.txt, 03-samll-01.txt, 04-max-id-01.txt, 05-max-rand-01.txt, 05-max-rand-02.txt, 05-max-rand-03.txt, 05-max-rand-04.txt, 05-max-rand-05.txt, 05-max-rand-06.txt, 05-max-rand-07.txt, 05-max-rand-08.txt, 05-max-rand-09.txt, 05-max-rand-10.txt, 06-divide-01.txt, 06-divide-02.txt, 06-divide-03.txt, 06-divide-04.txt, 06-divide-05.txt, 07-mid-rand-01.txt, 07-mid-rand-02.txt, 07-mid-rand-03.txt, 07-mid-rand-04.txt, 07-mid-rand-05.txt, 07-mid-rand-06.txt, 07-mid-rand-07.txt, 07-mid-rand-08.txt, 07-mid-rand-09.txt, 07-mid-rand-10.txt, 08-reverse-01.txt, 08-reverse-02.txt, 08-reverse-03.txt, 08-reverse-04.txt, 08-reverse-05.txt, 09-reverse-noise-01.txt, 09-reverse-noise-02.txt, 10-id-noise-01.txt, 10-id-noise-02.txt, 11-big-M-01.txt, 11-big-M-02.txt, 11-big-M-03.txt, 11-big-M-04.txt
ケース名 結果 実行時間 メモリ
01-sample-01.txt AC 1 ms 3608 KiB
02-min-01.txt AC 23 ms 3604 KiB
03-samll-01.txt AC 21 ms 3516 KiB
04-max-id-01.txt AC 21 ms 5524 KiB
05-max-rand-01.txt AC 26 ms 5348 KiB
05-max-rand-02.txt AC 26 ms 5444 KiB
05-max-rand-03.txt AC 26 ms 5420 KiB
05-max-rand-04.txt AC 27 ms 5420 KiB
05-max-rand-05.txt AC 26 ms 5492 KiB
05-max-rand-06.txt AC 26 ms 5392 KiB
05-max-rand-07.txt AC 27 ms 5584 KiB
05-max-rand-08.txt AC 27 ms 5432 KiB
05-max-rand-09.txt AC 27 ms 5436 KiB
05-max-rand-10.txt AC 26 ms 5468 KiB
06-divide-01.txt AC 24 ms 5444 KiB
06-divide-02.txt AC 23 ms 5432 KiB
06-divide-03.txt AC 24 ms 5396 KiB
06-divide-04.txt AC 24 ms 5444 KiB
06-divide-05.txt AC 23 ms 5348 KiB
07-mid-rand-01.txt AC 20 ms 3560 KiB
07-mid-rand-02.txt AC 21 ms 3496 KiB
07-mid-rand-03.txt AC 21 ms 3468 KiB
07-mid-rand-04.txt AC 21 ms 3560 KiB
07-mid-rand-05.txt AC 20 ms 3556 KiB
07-mid-rand-06.txt AC 20 ms 3556 KiB
07-mid-rand-07.txt AC 20 ms 3604 KiB
07-mid-rand-08.txt AC 20 ms 3560 KiB
07-mid-rand-09.txt AC 20 ms 3496 KiB
07-mid-rand-10.txt AC 20 ms 3564 KiB
08-reverse-01.txt AC 20 ms 5432 KiB
08-reverse-02.txt AC 20 ms 5348 KiB
08-reverse-03.txt AC 20 ms 5432 KiB
08-reverse-04.txt AC 20 ms 5416 KiB
08-reverse-05.txt AC 19 ms 3836 KiB
09-reverse-noise-01.txt AC 20 ms 5528 KiB
09-reverse-noise-02.txt AC 20 ms 5388 KiB
10-id-noise-01.txt AC 20 ms 5504 KiB
10-id-noise-02.txt AC 21 ms 5448 KiB
11-big-M-01.txt AC 26 ms 5448 KiB
11-big-M-02.txt AC 27 ms 5396 KiB
11-big-M-03.txt AC 27 ms 5588 KiB
11-big-M-04.txt AC 27 ms 5436 KiB