結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー daiota
提出日時 2026-04-19 02:26:59
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,605 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,539 ms
コンパイル使用メモリ 214,736 KB
実行使用メモリ 30,320 KB
平均クエリ数 10.75
最終ジャッジ日時 2026-04-19 02:27:16
合計ジャッジ時間 13,987 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18 WA * 54
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i=0;i<ll(n);i++)
















int main(void){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	ll i,j;




	ll N;
	cin >> N;


	vector<ll> v(N,-1);
	ll c=0,x=-1,p=-1;
	for(i=N-2;i>=0;i--){

		cout << "? " << i << ' ' << N-1 << endl;
		cout.flush();
		c++;

		cin >> p;

		if(p==0){
			v[i]=0;
			continue;
		}
		else{
			x=i;
			break;
		}

	}


	if(x==-1){
		cout << "! " << -1 << endl;
		cout.flush();
		return 0;
	}

	bool f=false;
	if(p==1){
		v[i]=1;
		v[N-1]=1;
		f=true;
	}
	else if(p==25){
		v[i]=5;
		v[N-1]=5;
		f=true;
	}
	else if(p==49){
		v[i]=7;
		v[N-1]=7;
		f=true;
	}
	else if(p==64){
		v[i]=8;
		v[N-1]=8;
		f=true;;
	}
	else if(p==81){
		v[i]=9;
		v[N-1]=9;
		f=true;
	}




	if(f){

		for(i=N-1;i>=0;i--){
			if(v[i]!=-1) continue;

			cout << "? " << i << ' ' << N-1 << endl;
			cout.flush();
			c++;

			ll r;
			cin >> r;

			v[i]=r/v[N-1];
		}

		if(c<=0){
			cout << "! ";
			for(i=N-1;i>=0;i--) cout << v[i];
			cout << endl;
			cout.flush();
		}
		else{
			cout << "! " << -1 << endl;
			cout.flush();
		}

		return 0;

	}




	ll y=-1,q=-1;
	for(i=x-1;i>=0;i--){

		cout << "? " << i << ' ' << N-1 << endl;
		cout.flush();
		c++;

		cin >> q;

		if(q==0){
			v[i]=0;
			continue;
		}
		else{
			y=i;
			break;
		}

	}


	if(y==-1){
		cout << "! " << -1 << endl;
		cout.flush();
		return 0;
	}


	if(q==1){
		v[i]=1;
		v[N-1]=1;
		v[x]=p;
		f=true;
	}
	else if(q==25){
		v[i]=5;
		v[N-1]=5;
		v[x]=p/5;
		f=true;
	}
	else if(q==49){
		v[i]=7;
		v[N-1]=7;
		v[x]=p/7;
		f=true;
	}
	else if(q==64){
		v[i]=8;
		v[N-1]=8;
		v[x]=p/8;
		f=true;;
	}
	else if(q==81){
		v[i]=9;
		v[N-1]=9;
		v[x]=p/9;
		f=true;
	}




	if(f){

		for(i=N-1;i>=0;i--){
			if(v[i]!=-1) continue;

			cout << "? " << i << ' ' << N-1 << endl;
			cout.flush();
			c++;

			ll r;
			cin >> r;

			v[i]=r/v[N-1];
		}

		if(c<=0){
			cout << "! ";
			for(i=N-1;i>=0;i--) cout << v[i];
			cout << endl;
			cout.flush();
		}
		else{
			cout << "! " << -1 << endl;
			cout.flush();
		}

		return 0;

	}




	cout << "? " << y << ' ' << x << endl;
	cout.flush();
	c++;

	ll s;
	cin >> s;

	v[N-1]=(ll)sqrt(1.0*p*q/s);
	v[x]=p/v[N-1];
	v[y]=q/v[N-1];


	for(i=N-1;i>=0;i--){
		if(v[i]!=-1) continue;

		cout << "? " << i << ' ' << N-1 << endl;
		cout.flush();
		c++;

		ll r;
		cin >> r;

		v[i]=r/v[N-1];
	}

	if(c<=0){
		cout << "! ";
		for(i=N-1;i>=0;i--) cout << v[i];
		cout << endl;
		cout.flush();
	}
	else{
		cout << "! " << -1 << endl;
		cout.flush();
	}










	return 0;

}
0