#1162149 (C++23) No.3519 A/B問題

• 問題: No.3519 A/B問題
• ユーザー: TKTYI
• 提出日時: 2026-05-01 21:36:50
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 103 ms / 2,000 ms
• コード長: 5,527 bytes
• コンパイル時間: 5,708 ms
• コンパイル使用メモリ: 384,760 KB
• 実行使用メモリ: 30,064 KB
• 平均クエリ数: 333.10
• 最終ジャッジ日時: 2026-05-01 21:37:03
• 合計ジャッジ時間: 10,447 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
other	AC * 30

ソースコード

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vvvl> vvvvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
typedef pair<ll,ppl> pppl;
typedef pair<ll,pppl> pppppl;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
#define F first
#define S second
#define bs(A,x) binary_search(all(A),x)
#define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin())
#define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin())
#define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x))
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
//*
using mint=modint998244353;
const ll mod=998244353;
//*/
/*
using mint=modint1000000007;
const ll mod=1000000007;
//*/
//using mint=modint;
//*
typedef vector<mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
typedef vector<vvvm> vvvvm;
ostream&operator<<(ostream&os,mint a){os<<a.val();return os;}
istream&operator>>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;}
//*/
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>p){os<<p.F<<" "<<p.S;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,0,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
struct bigint{
  bool neg;
  vector<int>d;
  bigint(){neg=false;}
  bigint(__int128 x){
    neg=(x<0);
    if(neg)x=-x;
    while(x>0){d.push_back(x%10);x/=10;}
  }
  int operator[](int k){return d[k];}
  int size(){return d.size();}
};
bool operator==(bigint A,bigint B){return A.neg==B.neg&&A.d==B.d;}
bool operator!=(bigint A,bigint B){return!(A==B);}
bool operator<(bigint A,bigint B){
  if(A.neg&&B.neg){A.neg=B.neg=false;return!(A<B);}
  if(A.neg)return true;
  if(B.neg)return false;
  int N1=A.size(),N2=B.size();
  if(N1!=N2)return N1<N2;
  for(int i=N1-1;i>=0;i--)if(A[i]!=B[i])return A[i]<B[i];
  return false;
}
bool operator<=(bigint A,bigint B){return A<B||A==B;}
bool operator>(bigint A,bigint B){return B<A;}
bigint operator-(bigint A){if(A.size())A.neg=!A.neg;return A;}
bigint operator+(bigint A,bigint B);
bigint operator-(bigint A,bigint B);
bigint operator+(bigint A,bigint B){
  if(B.neg)return A-(-B);
  if(A.neg){A.neg=false;if(B<A)return-(A-B);return B-A;}
  int N1=A.size(),N2=B.size(),N=max(N1,N2)+1;
  bigint C;
  C.d=vector<int>(N,0);
  for(int i=0;i<N1;i++)C.d[i]+=A[i];
  for(int i=0;i<N2;i++)C.d[i]+=B[i];
  for(int i=0;i<N-1;i++)if(C[i]>=10)C.d[i+1]++,C.d[i]-=10;
  if(C.size()&&C[N-1]==0)C.d.pop_back();
  return C;
}
bigint operator-(bigint A,bigint B){
  if(B.neg)return A+(-B);
  if(A.neg)return-((-A)+B);
  if(A<B)return-(B-A);
  int N1=A.size(),N2=B.size();
  bigint C=A;
  for(int i=0;i<N2;i++)C.d[i]-=B[i];
  for(int i=0;i<N1-1;i++)if(C[i]<0)C.d[i+1]--,C.d[i]+=10;
  while(C.size()&&C.d.back()==0)C.d.pop_back();
  return C;
}
bigint operator*(bigint A,bigint B){
  if(A.size()==0)return A;
  if(B.size()==0)return B;
  bool neg=A.neg^B.neg;
  int N1=A.size(),N2=B.size(),N=N1+N2;
  bigint C;
  C.d=vector<int>(N,0);
  for(int i=0;i<N1;i++)for(int j=0;j<N2;j++)C.d[i+j]+=A[i]*B[j];
  for(int i=0;i<N-1;i++)C.d[i+1]+=C[i]/10,C.d[i]%=10;
  while(C.size()&&C.d.back()==0)C.d.pop_back();
  if(neg)C.neg=true;
  return C;
}
pair<bigint, bigint> divmod(bigint A, bigint B){
  int N1 = A.size();
  int N2 = B.size();
  bigint Q;
  for (int i = N1 - N2; i >= 0; i--){
  	int q = 0;
  	if (A.size() >= N2 + i){
  	  N1 = A.size();
      bigint C;
      C.d = vector<int>(N1 - i);
      for (int j = 0; j < N1 - i; j++){
        C.d[j] = A[i + j];
      }
      for (int j = 1; j <= 9; j++){
        if (B * j <= C){
          q = j;
        } else {
          break;
        }
      }
    }
    Q.d.push_back(q);
    bigint B2 = B * q;
    int M = B2.size();
    bigint B3;
    B3.d = vector<int>(M + i, 0);
    for (int j = 0; j < M; j++){
      B3.d[i + j] = B2[j];
    }
    while (B3.size() >= 2 && B3.d.back() == 0){
      B3.d.pop_back();
    }
    A = A - B3;
  }
  if (Q.size() == 0){
    Q.d.push_back(0);
  }
  reverse(Q.d.begin(), Q.d.end());
  if (Q.size() >= 2 && Q.d.back() == 0){
    Q.d.pop_back();
  }
  return make_pair(Q, A);
}
bigint operator /(bigint A, bigint B){
  return divmod(A, B).first;
}
bigint operator %(bigint A, bigint B){
  return divmod(A, B).second;
}
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  bigint l=0,r=1;
  rep(i,0,100)r=r*10;
  r=r+1;
  while(l+1<r){
    auto m=(l+r)/2;
    cout<<"? 1 ";
    auto d=m-l;
    rrep(i,0,sz(d.d))cout<<d.d[i];
    cout<<endl;
    char c;cin>>c;
    if(c=='='){
      if(m==0)cout<<"! 0"<<endl;
      else{
        cout<<"! ";
        rrep(i,0,sz(m.d))cout<<m.d[i];
        cout<<endl;
      }
      return 0;
    }
    if(c=='<')r=m;
    else l=m;
  }
  if(l==0)cout<<"! 0"<<endl;
  else{
    cout<<"! ";
    rrep(i,0,sz(l.d))cout<<l.d[i];
    cout<<endl;
  }
  return 0;
}