結果

問題 No.1306 Exactly 2 Digits
コンテスト
ユーザー 沙耶花
提出日時 2020-12-03 16:57:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 523 ms / 2,000 ms
コード長 2,102 bytes
コンパイル時間 2,337 ms
コンパイル使用メモリ 213,212 KB
最終ジャッジ日時 2025-01-16 14:28:44
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 123
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:82:37: warning: ‘y’ may be used uninitialized [-Wmaybe-uninitialized]
   82 |                                 int y;
      |                                     ^

ソースコード

diff # 

#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;
}
0