#588660 (C++17) No.1306 Exactly 2 Digits

提出ソース

結果

問題	No.1306 Exactly 2 Digits
ユーザー	沙耶花
提出日時	2020-12-03 16:57:32
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	556 ms / 2,000 ms
コード長	2,102 bytes
コンパイル時間	2,535 ms
コンパイル使用メモリ	218,388 KB
実行使用メモリ	24,372 KB
平均クエリ数	1236.78
最終ジャッジ日時	2023-09-24 08:22:16
合計ジャッジ時間	25,427 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	28 ms 23,424 KB
testcase_01	AC	26 ms 23,400 KB
testcase_02	AC	26 ms 23,652 KB
testcase_03	AC	26 ms 24,240 KB
testcase_04	AC	25 ms 24,240 KB
testcase_05	AC	25 ms 24,348 KB
testcase_06	AC	26 ms 24,120 KB
testcase_07	AC	26 ms 23,640 KB
testcase_08	AC	26 ms 24,348 KB
testcase_09	AC	25 ms 23,652 KB
testcase_10	AC	25 ms 23,364 KB
testcase_11	AC	26 ms 23,448 KB
testcase_12	AC	25 ms 23,628 KB
testcase_13	AC	26 ms 24,084 KB
testcase_14	AC	26 ms 23,700 KB
testcase_15	AC	26 ms 24,288 KB
testcase_16	AC	26 ms 23,508 KB
testcase_17	AC	26 ms 24,360 KB
testcase_18	AC	27 ms 24,372 KB
testcase_19	AC	26 ms 23,580 KB
testcase_20	AC	26 ms 24,252 KB
testcase_21	AC	26 ms 23,400 KB
testcase_22	AC	26 ms 24,072 KB
testcase_23	AC	25 ms 23,664 KB
testcase_24	AC	27 ms 23,652 KB
testcase_25	AC	26 ms 23,532 KB
testcase_26	AC	27 ms 23,400 KB
testcase_27	AC	26 ms 23,460 KB
testcase_28	AC	27 ms 23,664 KB
testcase_29	AC	27 ms 23,448 KB
testcase_30	AC	26 ms 24,252 KB
testcase_31	AC	25 ms 23,652 KB
testcase_32	AC	27 ms 24,336 KB
testcase_33	AC	27 ms 23,376 KB
testcase_34	AC	27 ms 23,520 KB
testcase_35	AC	27 ms 24,048 KB
testcase_36	AC	27 ms 24,312 KB
testcase_37	AC	28 ms 24,324 KB
testcase_38	AC	27 ms 24,000 KB
testcase_39	AC	27 ms 24,276 KB
testcase_40	AC	28 ms 24,336 KB
testcase_41	AC	27 ms 23,412 KB
testcase_42	AC	28 ms 24,348 KB
testcase_43	AC	27 ms 23,688 KB
testcase_44	AC	28 ms 23,820 KB
testcase_45	AC	29 ms 23,664 KB
testcase_46	AC	29 ms 23,820 KB
testcase_47	AC	30 ms 23,820 KB
testcase_48	AC	32 ms 23,460 KB
testcase_49	AC	33 ms 23,568 KB
testcase_50	AC	33 ms 23,688 KB
testcase_51	AC	37 ms 23,580 KB
testcase_52	AC	38 ms 23,364 KB
testcase_53	AC	39 ms 24,024 KB
testcase_54	AC	42 ms 23,688 KB
testcase_55	AC	41 ms 23,448 KB
testcase_56	AC	50 ms 24,348 KB
testcase_57	AC	49 ms 24,024 KB
testcase_58	AC	46 ms 24,072 KB
testcase_59	AC	58 ms 23,868 KB
testcase_60	AC	50 ms 24,024 KB
testcase_61	AC	60 ms 23,364 KB
testcase_62	AC	64 ms 23,688 KB
testcase_63	AC	76 ms 23,568 KB
testcase_64	AC	55 ms 24,024 KB
testcase_65	AC	73 ms 24,264 KB
testcase_66	AC	68 ms 23,868 KB
testcase_67	AC	70 ms 23,400 KB
testcase_68	AC	100 ms 23,688 KB
testcase_69	AC	91 ms 23,652 KB
testcase_70	AC	145 ms 23,832 KB
testcase_71	AC	85 ms 23,364 KB
testcase_72	AC	136 ms 23,352 KB
testcase_73	AC	159 ms 24,336 KB
testcase_74	AC	111 ms 24,348 KB
testcase_75	AC	174 ms 23,448 KB
testcase_76	AC	185 ms 23,364 KB
testcase_77	AC	214 ms 23,580 KB
testcase_78	AC	147 ms 24,324 KB
testcase_79	AC	268 ms 23,628 KB
testcase_80	AC	204 ms 23,628 KB
testcase_81	AC	271 ms 24,336 KB
testcase_82	AC	244 ms 23,556 KB
testcase_83	AC	193 ms 23,868 KB
testcase_84	AC	194 ms 23,568 KB
testcase_85	AC	314 ms 23,820 KB
testcase_86	AC	243 ms 23,364 KB
testcase_87	AC	284 ms 23,400 KB
testcase_88	AC	233 ms 23,688 KB
testcase_89	AC	366 ms 23,532 KB
testcase_90	AC	498 ms 24,048 KB
testcase_91	AC	407 ms 24,252 KB
testcase_92	AC	340 ms 24,360 KB
testcase_93	AC	295 ms 23,652 KB
testcase_94	AC	139 ms 24,024 KB
testcase_95	AC	339 ms 23,664 KB
testcase_96	AC	348 ms 23,412 KB
testcase_97	AC	169 ms 23,652 KB
testcase_98	AC	128 ms 23,688 KB
testcase_99	AC	296 ms 24,204 KB
testcase_100	AC	335 ms 23,508 KB
testcase_101	AC	438 ms 23,568 KB
testcase_102	AC	297 ms 23,856 KB
testcase_103	AC	300 ms 24,324 KB
testcase_104	AC	240 ms 24,084 KB
testcase_105	AC	363 ms 23,364 KB
testcase_106	AC	404 ms 23,652 KB
testcase_107	AC	312 ms 24,048 KB
testcase_108	AC	447 ms 23,508 KB
testcase_109	AC	167 ms 24,060 KB
testcase_110	AC	147 ms 23,448 KB
testcase_111	AC	141 ms 23,628 KB
testcase_112	AC	135 ms 23,412 KB
testcase_113	AC	288 ms 23,700 KB
testcase_114	AC	149 ms 24,048 KB
testcase_115	AC	248 ms 23,472 KB
testcase_116	AC	556 ms 23,808 KB
testcase_117	AC	373 ms 23,652 KB
testcase_118	AC	542 ms 24,264 KB
testcase_119	AC	387 ms 23,400 KB
testcase_120	AC	154 ms 24,336 KB
testcase_121	AC	241 ms 23,868 KB
testcase_122	AC	186 ms 24,024 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: 関数 ‘void solve()’ 内:
main.cpp:82:37: 警告: ‘y’ may be used uninitialized [-Wmaybe-uninitialized]
   82 |                                 int y;
      |                                     ^

ソースコード

raw source code

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000
vector<int> a;
int N;
pair<int,int> calc(int a,int b){
	int x = a/N - b/N;
	int y = a%N - b%N;
	if(x>y)swap(x,y);
	
	return make_pair(x,y);
}

pair<int,int> query(int i,int j){
	cout<<"? "<<i<<' '<<j<<endl;
	
	//cout<<calc(a[i-1],a[j-1]).first<<' '<<calc(a[i-1],a[j-1]).second<<endl;
	//return calc(a[i-1],a[j-1]);
	
	int r0,r1;
	cin>>r0>>r1;
	
	return make_pair(r0,r1);
}



void answer(vector<int> ans){
	cout<<"!";
	rep(i,ans.size()){
		cout<<' '<<ans[i];
	}
	cout<<endl;
}

void solve(){
	vector<int> ans(N*N-N,-1);
	vector<pair<int,int>> ret;
	rep(i,ans.size()){
		if(i==0)continue;
		ret.push_back(query(1,i+1));
	}
	
	{
		vector<pair<int,int>> temp = ret;
		sort(temp.begin(),temp.end());
		rep(i,N*N-N){
			vector<pair<int,int>> X;
			rep(j,N*N-N){
				if(i==j)continue;
				X.push_back(calc(i+N,j+N));
			}
			sort(X.begin(),X.end());
			if(X==temp){
				ans[0] = i+N;
				break;
			}
		}
	}
		
	map<int,vector<int>> mp;
	rep(i,ret.size()){
		rep(j,N*N-N){
			if(ret[i]==calc(ans[0],j+N)){
				mp[j+N].push_back(i+1);
				break;
			}
		}		
	}

	while(mp.size()!=0){

		for(auto it = mp.begin();it!=mp.end();){
			if(it->second.size()==1){
				ans[it->second[0]] = it->first;
				it = mp.erase(it);
			}
			else{
				int x = it->first;
				int y;
				for(int i=x+1;i<N*N;i++){
					if(calc(ans[0],x)==calc(ans[0],i)){
						y = i;
						break;
					}
				}

				bool f = false;
				rep(i,ans.size()){
					if(ans[i]==-1)continue;
					if(calc(ans[i],x)!=calc(ans[i],y)){
						pair<int,int> ret = query(i+1,it->second[0]+1);
						if(ret==calc(ans[i],x)){
							ans[it->second[0]] = x;
							ans[it->second[1]] = y;
						}
						else{
							ans[it->second[0]] = y;
							ans[it->second[1]] = x;
						}
						f=true;
						break;
					}
				}
				if(f){
					it = mp.erase(it);
				}
				else{
					it++;
				}
			}
		}
	}
	
	answer(ans);
	
}

int main(){
	
	cin>>N;
	/*
	a.resize(N*N-N);
	rep(i,N*N-N){
		cin>>a[i];
	}
	*/
	
	solve();		
	
	return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード