結果

問題 No.3347 Guess The Array
コンテスト
ユーザー Nyaa Uruzu
提出日時 2025-11-21 05:41:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 350 ms / 2,000 ms
コード長 3,848 bytes
コンパイル時間 3,809 ms
コンパイル使用メモリ 301,288 KB
実行使用メモリ 26,240 KB
平均クエリ数 3160.46
最終ジャッジ日時 2025-11-21 05:42:08
合計ジャッジ時間 18,174 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (ll i=0;i<(ll)n;i++)
#define rrep(i,n) for (ll i=(n)-1;i>=(ll)0;i--)
#define loop(i,m,n) for(ll i=m;i<=(ll)n;i++)
#define rloop(i,m,n) for(ll i=m;i>=(ll)n;i--)
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vdbg(a) rep(ii,a.size()){cout<<a[ii]<<" ";}cout<<endl;
#define vpdbg(a) rep(ii,a.size()){cout<<"{"<<a[ii].first<<","<<a[ii].second<<"} ";}cout<<endl;
#define vvdbg(a) rep(ii,a.size()){rep(jj,a[ii].size()){cout<<a[ii][jj]<<" ";}cout<<endl;}
#define setdbg(a) for(const auto & ii:a){cout<<ii<<" ";}cout<<endl;
#define inf 4000000000000000000LL
#define mod 998244353LL
//#define mod 1000000007LL
#define eps 0.000000001
random_device rnd;// 非決定的な乱数生成器
mt19937 mt(rnd());// メルセンヌ・ツイスタの32ビット版、引数は初期シード

//#include<boost/multiprecision/cpp_int.hpp>
//#define bbi boost::multiprecision::cpp_int
//#include<atcoder/lazysegtree>


//整数同士の累乗の計算をする。
ll power(ll A, ll B) {
	ll result = 1;
	for (ll i=0;i<B;i++){
		result *= A;
	}
	return result;
}

//底がaの対数xを計算。ただし小数点は繰り上げ。
ll logax(ll a, ll x){
	if(x<=1)return 0;
	ll result = 1;
	ll power = 1;
	while (power < (x+a-1) / a){
		power *= a;
		result++;
	}
	return result;
}

//グリッド問題等用
vl dx={1,0,-1,0};
vl dy={0,1,0,-1};

//powerとlogが前提条件
//セグ木,乗せる値の型が必要
template<typename T>
struct SegTree{
	ll size;
	ll tall;
	vector<T> data;
	function<T(T,T)> p;
	//セグ木に乗せる値の初期値をa配列にし、putの関数をセグ木に乗せる、dをデフォルト値に。
	SegTree(vector<T> a,function<T(T,T)> put,T d) : data(power(2,logax(2,a.size())+1)) {
		size = data.size()/2;
		tall=logax(2,size)+1;
		p=put;
		ll tmp=size;
		data = vector<T>(size*2,d);
		while(tmp!=0){
			if(tmp==size)rep(i,a.size())data[tmp+i]=a[i];
			else rep(i,tmp) data[tmp+i]=p(data[2*(tmp+i)],data[2*(tmp+i)+1]);
			tmp/=2;
		}
	}
	//更新、t番目の値をxにする。
	void update(ll t,T x){
		t+=size;
		while(t!=0){
			if(t>=size)data[t]=x;
			else data[t]=p(data[2*t],data[2*t+1]);
			t/=2;
		}
	}
	//取得、l~r区間内の評価値を取得する。
	T get(ll l,ll r){
		//lとrが範囲外なら範囲内に正す
		l=max(0LL,l);
		r=min(r,size-1);
		r++;
		T ans=data[0];
		ll pos=l+size;
		ll wid=1;
		//出来る限り上に上げきる。
		while(l+(wid*2)<=r){
			while(l%(wid*2)==0&&l+(wid*2)<=r)pos/=2,wid*=2;
			ans=p(ans,data[pos]);
			pos++;
			l+=wid;
		}
		//上げ終わったので今度は下げる
		while(l!=r){
			while(l+wid>r)pos*=2,wid/=2;
			ans=p(ans,data[pos]);
			pos++;
			l+=wid;
		}
		return ans;
	}
};


ll n;

map<vl,bool> cash;
bool query(vl a){
	if(a.size()>n)return false;
	if(cash.count(a))return cash[a];
	cout<<"? "<<a.size();

	for(auto val:a){
		cout<<" "<<val;
	}
	cout<<endl;
	string ans;
	cin>>ans;
	bool tmp;
	if(ans=="Yes")tmp=true;
	else tmp=false;
	cash[a]=tmp;
	return cash[a];
}

//メイン
int main(){
	cin>>n;
	priority_queue<pair<ll,vl>> list;
	loop(i,1,n){
		ll tmp=0;
		rep(j,inf){
			vl q(tmp+1,i);
			if(!query(q))break;
			tmp++;
		}
		vl vt;
		rep(j,tmp)vt.push_back(i);
		list.push({-tmp,vt});
	}
	while(list.top().first==0)list.pop();

	while(list.size()>1){
		vl a=list.top().second;
		list.pop();
		vl b=list.top().second;
		list.pop();

		vl ans=b;

		ll index=0;
		rep(i,b.size()){
			while(index!=a.size()){
				ans.insert(ans.begin()+i+index,a[index]);
				if(query(ans)){
					index++;
				}else{
					ans.erase(ans.begin()+i+index);
					break;
				}
			}
		}
		while(index<a.size())ans.push_back(a[index]),index++;
		list.push({-ans.size(),ans});
	}
	vl ans=list.top().second;
	cout<<"! ";
	vdbg(ans);
	return 0;
}
0