結果

問題 No.2496 LCM between Permutations
ユーザー kotatsugamekotatsugame
提出日時 2023-10-09 13:30:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 105 ms / 2,000 ms
コード長 3,080 bytes
コンパイル時間 1,430 ms
コンパイル使用メモリ 112,184 KB
実行使用メモリ 24,480 KB
平均クエリ数 776.38
最終ジャッジ日時 2023-10-09 13:30:50
合計ジャッジ時間 5,236 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
23,388 KB
testcase_01 AC 25 ms
24,024 KB
testcase_02 AC 25 ms
23,664 KB
testcase_03 AC 26 ms
23,412 KB
testcase_04 AC 25 ms
24,036 KB
testcase_05 AC 26 ms
24,024 KB
testcase_06 AC 26 ms
23,376 KB
testcase_07 AC 26 ms
24,012 KB
testcase_08 AC 25 ms
23,520 KB
testcase_09 AC 26 ms
24,480 KB
testcase_10 AC 25 ms
24,348 KB
testcase_11 AC 25 ms
23,652 KB
testcase_12 AC 25 ms
24,036 KB
testcase_13 AC 26 ms
23,520 KB
testcase_14 AC 26 ms
23,388 KB
testcase_15 AC 30 ms
23,364 KB
testcase_16 AC 31 ms
23,352 KB
testcase_17 AC 32 ms
24,312 KB
testcase_18 AC 72 ms
23,616 KB
testcase_19 AC 67 ms
24,036 KB
testcase_20 AC 72 ms
23,520 KB
testcase_21 AC 74 ms
24,360 KB
testcase_22 AC 70 ms
23,640 KB
testcase_23 AC 101 ms
23,592 KB
testcase_24 AC 66 ms
23,640 KB
testcase_25 AC 87 ms
23,364 KB
testcase_26 AC 103 ms
23,604 KB
testcase_27 AC 105 ms
24,036 KB
testcase_28 AC 103 ms
24,324 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:95:26: 警告: ‘b’ may be used uninitialized [-Wmaybe-uninitialized]
   95 |                 A[a]=B[b]=1;
      |                      ~~~~^~
main.cpp:85:23: 備考: ‘b’ はここで定義されています
   85 |                 int a,b;
      |                       ^
main.cpp:95:21: 警告: ‘a’ may be used uninitialized [-Wmaybe-uninitialized]
   95 |                 A[a]=B[b]=1;
      |                 ~~~~^~~~~~~
main.cpp:85:21: 備考: ‘a’ はここで定義されています
   85 |                 int a,b;
      |                     ^

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cassert>
#include<cstdlib>
using namespace std;
const bool debug=false;
int gcd(int a,int b)
{
	while(b)
	{
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}
bool isp[1001];
int N;
int A[1000],B[1000];
int aA[1000],aB[1000];
int ask(int i,int j)
{
	cout<<"? "<<i+1<<" "<<j+1<<endl;
	if(debug)return aA[i]*aB[j]/gcd(aA[i],aB[j]);
	int x;cin>>x;
	return x;
}
void answer()
{
	cout<<"!";
	for(int i=0;i<N;i++)cout<<" "<<A[i];
	for(int i=0;i<N;i++)cout<<" "<<B[i];
	cout<<endl;
	if(debug)
	{
		for(int i=0;i<N;i++)if(aA[i]!=A[i]||aB[i]!=B[i])
		{
			cout<<"WA"<<endl;
			exit(1);
		}
		cout<<"AC"<<endl;
	}
	exit(0);
}
#include<random>
mt19937 rng;
void setup()
{
	random_device seed_gen;
	unsigned int seed=seed_gen();
	//seed=1604191338;
	if(debug)cout<<"seed = "<<seed<<endl;
	rng=mt19937(seed);
	if(!debug)return;
	N=rng()%100+1;
	for(int i=0;i<N;i++)aA[i]=aB[i]=i+1;
	shuffle(aA,aA+N,rng);
	shuffle(aB,aB+N,rng);
	cout<<"answer =";
	for(int i=0;i<N;i++)cout<<" "<<aA[i];
	for(int i=0;i<N;i++)cout<<" "<<aB[i];
	cout<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	setup();
	if(!debug)cin>>N;
	for(int i=2;i<=N;i++)isp[i]=true;
	for(int i=2;i<=N;i++)if(isp[i])
	{
		for(int j=i+i;j<=N;j+=i)isp[j]=false;
	}
	if(N==1)
	{
		A[0]=B[0]=1;
		answer();
	}
	if(N==2)
	{
		bool fn=false;
		int a,b;
		for(int i=0;!fn&&i<2;i++)for(int j=0;!fn&&j<2;j++)
		{
			if(ask(i,j)==1)
			{
				a=i,b=j;
				fn=true;
			}
		}
		A[0]=A[1]=B[0]=B[1]=2;
		A[a]=B[b]=1;
		answer();
	}
	int T[1000];
	int mini=0;
	for(int i=0;i<N;i++)
	{
		T[i]=ask(0,i);
		if(T[mini]>T[i])mini=i;
	}
	A[0]=T[mini];
	map<int,vector<int> >LtoB;
	for(int b=1;b<=N;b++)
	{
		int L=A[0]/gcd(A[0],b)*b;
		LtoB[L].push_back(b);
	}
	vector<pair<int,int> >Ps,nPs;
	for(int i=0;i<N;i++)
	{
		assert(LtoB.find(T[i])!=LtoB.end());
		if(LtoB[T[i]].size()==1)
		{
			int p=B[i]=LtoB[T[i]][0];
			if(isp[p])
			{
				Ps.push_back(make_pair(p,i));
			}
			else
			{
				nPs.push_back(make_pair(p,i));
			}
		}
	}
	sort(Ps.begin(),Ps.end());
	assert(!Ps.empty());
	assert(Ps.back().first*3>N);
	int P=Ps.back().first,Pi=Ps.back().second;
	for(int i=1;i<N;i++)
	{
		int v=ask(i,Pi);
		assert(v%P==0);
		A[i]=v/P;
	}
	vector<int>one;
	for(int i=0;i<N;i++)if(A[i]==1)one.push_back(i);
	assert(one.size()==2);
	vector<int>test;
	int ONE;
	for(int i=0;i<N;i++)if(i!=Pi)test.push_back(i);
	assert(test.size()>=2);
	if(ask(one[0],test[0])%P!=0||ask(one[0],test[1])%P!=0)ONE=one[0];
	else ONE=one[1];
	A[one[0]+one[1]-ONE]=P;
	for(int i=0;i<N;i++)if(B[i]==0)B[i]=ask(ONE,i);
	if(P*2<=N)
	{
		assert((N==4&&A[0]==3)||(N==6&&A[0]==5)||(N==10&&A[0]==7));
		//[4, 3]
		//{1=>[1, 3], 2=>[2], 4=>[4]}
		//[6, 5]
		//{1=>[1, 5], 2=>[2], 3=>[3], 4=>[4], 6=>[6]}
		//[10, 7]
		//{1=>[1, 7], 2=>[2], 3=>[3], 4=>[4], 5=>[5], 6=>[6], 8=>[8], 9=>[9], 10=>[10]}
		vector<int>two;
		for(int i=0;i<N;i++)if(A[i]==2)two.push_back(i);
		assert(two.size()==2);
		int O=0;
		while(B[O]!=1)O++;
		if(ask(two[0],O)==2)A[two[1]]=2*P;
		else A[two[0]]=2*P;
	}
	answer();
}
0