#1162890 (C++23) No.3529 2p Teleportations

• 問題: No.3529 2p Teleportations
• ユーザー: askr58
• 提出日時: 2026-05-04 22:18:13
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 1,723 bytes
• コンパイル時間: 3,821 ms
• コンパイル使用メモリ: 349,080 KB
• 実行使用メモリ: 7,976 KB
• 最終ジャッジ日時: 2026-05-04 22:18:33
• 合計ジャッジ時間: 16,155 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 3 WA * 46

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

long long extgcd(long long a,long long b,long long& x,long long& y){
	if(b==0){
		x=1;y=0;
		return a;
	}
	long long d=extgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int ttt;
	cin>>ttt;
	while(ttt--){
		int n,p;
		cin>>n>>p;
		vector<int> a(n);
		for(int i=0;i<n;i++)cin>>a[i],a[i]--;
		vector<vector<vector<int>>> cycles(n+1);
		vector<bool> seen(n);
		for(int i=0;i<n;i++){
			if(seen[i])continue;
			int cur=a[i];
			seen[i]=true;
			vector<int> cycle({i});
			while(cur!=i){
				seen[cur]=true;
				cycle.push_back(cur);
				cur=a[cur];
			}
			cycles[cycle.size()].push_back(cycle);
		}
		vector<int> b(n,-1);
		for(int i=1;i<=n;i++){
			if(i%2==1){
				ll x,y;
				extgcd(2*p,i,x,y);
				if(x<0)x+=(-x+i-1)/i*i;
				x%=i;
				for(auto vec:cycles[i]){
					for(int j=0;j<i;j++){
						b[vec[j]]=vec[(j+x)%i];
					}
				}
				continue;
			}
			if(cycles[i].empty())continue;
			int m=cycles[i].size();
			for(int j=0;j<m;j+=2){
				if(j+1==m){
					ll x,y;
					extgcd(2*p,i-1,x,y);
					if(x<0)x+=(-x+i-2)/(i-1)*(i-1);
					x%=(i-1);
					auto vec=cycles[i][j];
					int z=vec.back();
					vec.pop_back();
					for(int k=0;k<i-1;k++)b[vec[k]]=vec[(k+x)%(i-1)];
					b[z]=vec[x];
					continue;
				}
				vector<int> big_cycle;
				for(int k=0;k<i;k++){
					big_cycle.push_back(cycles[i][j][k]);
					big_cycle.push_back(cycles[i][j+1][k]);
				}
				ll x,y;
				extgcd(p,2*i,x,y);
				if(x<0)x+=(-x+2*i-1)/(2*i)*(2*i);
				x%=2*i;
				for(int k=0;k<2*i;k++)b[big_cycle[k]]=big_cycle[(k+x)%(2*i)];
			}
		}
		for(int i=0;i<n;i++)cout<<b[i]+1<<(i+1==n?"":" ");
		cout<<endl;
	}
}