Submission #32601636

---

Source Code Expand

// vim:set foldmethod=marker foldlevel=0:
/* include {{{ */
#include <bits/stdc++.h>
#include <atcoder/all>
#ifdef _DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#endif
/* }}} */
/* utility {{{*/
using namespace atcoder;
using namespace std;

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)

// 注意: rep, rep2と同じ範囲を逆順にしたもの
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rrep2(i, s, n) for (ll i = (n)-1; i >= (ll)(s); i--)


using mint = modint998244353;
/* using mint = modint1000000007; */

using ll=long long;
using vll=vector<ll>;
using vvll=vector<vll>;
using vvvll=vector<vvll>;
using vs=vector<string>;
using vvs=vector<vs>;
using vb=vector<bool>;
using vvb=vector<vb>;
using vmd=vector<mint>;
using vvmd=vector<vmd>;
using vvvmd=vector<vvmd>;
using P = pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}

const ll INF = 1000000000000000000ll;
string YesNo(bool flag) { return flag ? "Yes" : "No"; }
/* }}} */

/////////////////////////////////////////////////////////////////

ll d(ll u, ll v) {
  u++; v++;
  cout<<"? "<<u<<" "<<v<<endl;
  ll ret;
  cin>>ret;
  return ret;
}

int main() {
  ll n;
  cin>>n;

  vll d0(n),d1(n);

  rep(i,n){
    if (i==0||i==1)continue;
    d0[i] = d(0, i);
  }
  rep(i,n){
    if (i==0||i==1)continue;
    d1[i] = d(1, i);
  }

  bool diff1=false,diff1under=true;
  // 0,1が隣接するかをチェック
  rep(i,n){
    if (i==0||i==1)continue;
    if (abs(d0[i]-d1[i]) > 1) {
      diff1under = false;
      break;
    }
    if (abs(d0[i]-d1[i]) == 1) {
      diff1 = true;
    }
  }

  bool neib = false;
  neib = diff1 && diff1under;
  // 0 - x - y - 1のパターンがあるかをチェック
  {
    ll x=-1,y=-1;
    rep(i,n){
      if (d0[i] == 1ll && d1[i] == 2ll) {
        x = i;
        break;
      }
    }
    rep(i,n){
      if (d0[i] == 2ll && d1[i] == 1ll) {
        y = i;
      }
    }
    if (x>0&&y>0) {
      ll dxy = d(x,y);
      if (dxy == 1ll) {
        neib = false;
      }
    }
  }

  ll ans;
  if (neib) {
    ans = 1ll;
  } else {
    ans = INF;
    rep(i,n){
      if (i==0||i==1)continue;
      chmin(ans, d0[i]+d1[i]);
    }
  }
  cout<<"! "<<ans<<endl;

  return 0;
}

Submission Info

Judge Result