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

提出ソース

結果

問題	No.1306 Exactly 2 Digits
ユーザー	沙耶花
提出日時	2020-12-03 16:57:32
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	556 ms / 2,000 ms
コード長	2,102 bytes
コンパイル時間	3,047 ms
コンパイル使用メモリ	220,524 KB
実行使用メモリ	25,556 KB
平均クエリ数	1236.78
最終ジャッジ日時	2024-07-17 08:45:27
合計ジャッジ時間	25,308 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	25 ms 25,196 KB
testcase_01	AC	23 ms 25,196 KB
testcase_02	AC	24 ms 24,836 KB
testcase_03	AC	23 ms 24,836 KB
testcase_04	AC	23 ms 24,836 KB
testcase_05	AC	23 ms 25,220 KB
testcase_06	AC	23 ms 24,836 KB
testcase_07	AC	23 ms 25,104 KB
testcase_08	AC	24 ms 24,964 KB
testcase_09	AC	23 ms 25,064 KB
testcase_10	AC	23 ms 24,580 KB
testcase_11	AC	24 ms 25,220 KB
testcase_12	AC	23 ms 25,220 KB
testcase_13	AC	23 ms 25,196 KB
testcase_14	AC	23 ms 25,196 KB
testcase_15	AC	23 ms 25,196 KB
testcase_16	AC	24 ms 24,812 KB
testcase_17	AC	24 ms 24,556 KB
testcase_18	AC	23 ms 25,196 KB
testcase_19	AC	24 ms 25,196 KB
testcase_20	AC	24 ms 24,812 KB
testcase_21	AC	23 ms 25,196 KB
testcase_22	AC	23 ms 25,196 KB
testcase_23	AC	24 ms 24,812 KB
testcase_24	AC	24 ms 25,196 KB
testcase_25	AC	24 ms 24,812 KB
testcase_26	AC	24 ms 24,940 KB
testcase_27	AC	24 ms 24,428 KB
testcase_28	AC	24 ms 25,196 KB
testcase_29	AC	24 ms 25,196 KB
testcase_30	AC	23 ms 24,556 KB
testcase_31	AC	23 ms 25,196 KB
testcase_32	AC	25 ms 24,812 KB
testcase_33	AC	24 ms 24,812 KB
testcase_34	AC	24 ms 24,812 KB
testcase_35	AC	24 ms 24,812 KB
testcase_36	AC	24 ms 25,196 KB
testcase_37	AC	23 ms 25,196 KB
testcase_38	AC	25 ms 25,452 KB
testcase_39	AC	25 ms 24,556 KB
testcase_40	AC	23 ms 24,556 KB
testcase_41	AC	24 ms 24,812 KB
testcase_42	AC	24 ms 25,064 KB
testcase_43	AC	24 ms 25,196 KB
testcase_44	AC	25 ms 25,196 KB
testcase_45	AC	25 ms 25,196 KB
testcase_46	AC	25 ms 24,812 KB
testcase_47	AC	27 ms 24,812 KB
testcase_48	AC	28 ms 24,940 KB
testcase_49	AC	29 ms 24,812 KB
testcase_50	AC	30 ms 24,812 KB
testcase_51	AC	33 ms 25,196 KB
testcase_52	AC	35 ms 24,556 KB
testcase_53	AC	36 ms 24,812 KB
testcase_54	AC	39 ms 24,808 KB
testcase_55	AC	40 ms 24,556 KB
testcase_56	AC	46 ms 24,812 KB
testcase_57	AC	45 ms 25,196 KB
testcase_58	AC	44 ms 24,812 KB
testcase_59	AC	54 ms 24,812 KB
testcase_60	AC	48 ms 24,940 KB
testcase_61	AC	59 ms 24,812 KB
testcase_62	AC	63 ms 24,940 KB
testcase_63	AC	74 ms 24,556 KB
testcase_64	AC	53 ms 25,196 KB
testcase_65	AC	71 ms 24,940 KB
testcase_66	AC	66 ms 25,556 KB
testcase_67	AC	68 ms 25,068 KB
testcase_68	AC	97 ms 24,928 KB
testcase_69	AC	91 ms 25,196 KB
testcase_70	AC	143 ms 25,068 KB
testcase_71	AC	85 ms 24,812 KB
testcase_72	AC	134 ms 24,940 KB
testcase_73	AC	155 ms 24,556 KB
testcase_74	AC	111 ms 25,196 KB
testcase_75	AC	170 ms 25,148 KB
testcase_76	AC	182 ms 25,196 KB
testcase_77	AC	214 ms 24,812 KB
testcase_78	AC	148 ms 25,196 KB
testcase_79	AC	274 ms 24,812 KB
testcase_80	AC	215 ms 24,556 KB
testcase_81	AC	272 ms 25,196 KB
testcase_82	AC	244 ms 24,556 KB
testcase_83	AC	191 ms 24,940 KB
testcase_84	AC	196 ms 24,812 KB
testcase_85	AC	318 ms 24,812 KB
testcase_86	AC	239 ms 25,068 KB
testcase_87	AC	283 ms 24,940 KB
testcase_88	AC	246 ms 24,556 KB
testcase_89	AC	365 ms 24,812 KB
testcase_90	AC	496 ms 25,112 KB
testcase_91	AC	405 ms 25,196 KB
testcase_92	AC	339 ms 25,196 KB
testcase_93	AC	296 ms 24,940 KB
testcase_94	AC	138 ms 24,940 KB
testcase_95	AC	340 ms 24,812 KB
testcase_96	AC	351 ms 24,812 KB
testcase_97	AC	173 ms 24,812 KB
testcase_98	AC	130 ms 24,812 KB
testcase_99	AC	296 ms 25,068 KB
testcase_100	AC	337 ms 24,940 KB
testcase_101	AC	438 ms 24,940 KB
testcase_102	AC	296 ms 25,068 KB
testcase_103	AC	298 ms 24,812 KB
testcase_104	AC	239 ms 24,812 KB
testcase_105	AC	364 ms 24,812 KB
testcase_106	AC	395 ms 24,812 KB
testcase_107	AC	311 ms 24,556 KB
testcase_108	AC	459 ms 24,556 KB
testcase_109	AC	173 ms 25,196 KB
testcase_110	AC	146 ms 24,940 KB
testcase_111	AC	141 ms 24,800 KB
testcase_112	AC	137 ms 24,812 KB
testcase_113	AC	293 ms 24,556 KB
testcase_114	AC	150 ms 25,196 KB
testcase_115	AC	250 ms 25,196 KB
testcase_116	AC	556 ms 24,812 KB
testcase_117	AC	373 ms 25,196 KB
testcase_118	AC	544 ms 24,556 KB
testcase_119	AC	390 ms 24,812 KB
testcase_120	AC	155 ms 25,196 KB
testcase_121	AC	240 ms 24,940 KB
testcase_122	AC	189 ms 24,812 KB

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

コンパイルメッセージ

main.cpp: In function 'void solve()':
main.cpp:82:37: warning: '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

結果

テストケース

コンパイルメッセージ

ソースコード