結果

問題 No.2252 Find Zero
ユーザー kztasakztasa
提出日時 2023-03-24 21:27:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 5,910 bytes
コンパイル時間 4,172 ms
コンパイル使用メモリ 233,408 KB
実行使用メモリ 24,660 KB
平均クエリ数 78.17
最終ジャッジ日時 2023-10-18 20:44:08
合計ジャッジ時間 6,723 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
24,660 KB
testcase_01 AC 75 ms
24,660 KB
testcase_02 AC 56 ms
24,660 KB
testcase_03 AC 65 ms
24,660 KB
testcase_04 AC 56 ms
24,660 KB
testcase_05 AC 54 ms
24,660 KB
testcase_06 AC 54 ms
24,660 KB
testcase_07 AC 54 ms
24,660 KB
testcase_08 AC 62 ms
24,660 KB
testcase_09 AC 65 ms
24,660 KB
testcase_10 AC 53 ms
24,660 KB
testcase_11 AC 54 ms
24,660 KB
testcase_12 AC 54 ms
24,660 KB
testcase_13 AC 54 ms
24,660 KB
testcase_14 AC 54 ms
24,660 KB
testcase_15 AC 54 ms
24,660 KB
testcase_16 AC 54 ms
24,660 KB
testcase_17 AC 55 ms
24,660 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h> 
#include <atcoder/all>
#define pub push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (ll i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (ll i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
using namespace atcoder;
using ll = long long; using dd = double;
using Pll = pair<ll, ll>;
using    vll = vector<   ll>; using   vdd = vector< dd>;
using   vvll = vector<  vll>; using  vvdd = vector<vdd>;
using  vvvll = vector< vvll>; using vvvdd = vector<vvdd>;
using vvvvll = vector<vvvll>;
using  vchar = vector< char>;
using vvchar = vector<vchar>;
using mint = modint998244353;
using mint2 = modint1000000007;
using  vmint = vector< mint>; using  vmint2 = vector< mint2>;
using vvmint = vector<vmint>; using vvmint2 = vector<vmint2>;

constexpr long long INF = (1LL << 60);
constexpr double EPS = 1e-9;
constexpr double PI = 3.141592653589;

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

template <typename T>
bool chmax(T& a, const T& b) {
	if (a < b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}

template <typename T>
bool chmin(T& a, const T& b) {
	if (a > b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}

template <typename T>
T sq(T x) {
	return x * x;
}

std::string zfill(int n, const int width)
{
	std::stringstream ss;
	ss << std::setw(width) << std::setfill('0') << n;
	return ss.str();
}





struct HLD {
    int n;
    vector<int> siz, top, dep, parent, in, out, seq;
    vector<vector<int>> adj;
    int cur;

    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 0;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root = 0) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1) {
            adj[u].erase(find(adj[u].begin(), adj[u].end(), parent[u]));
        }

        siz[u] = 1;
        for (auto& v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            }
            else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }

    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    int jump(int u, int k) {
        if (dep[u] < k) {
            return -1;
        }

        int d = dep[u] - k;

        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }

        return seq[in[u] - dep[u] + d];
    }

    bool isAncester(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }

    int rootedChild(int u, int v) {
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
            }) - 1;
        return *it;
    }

    int rootedSize(int u, int v) {
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return siz[v];
        }
        return n - siz[rootedChild(v, u)];
    }

    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};




bool isp(ll num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}



//N未満でNと互いに素な数の個数(オイラーのトーシェント関数)
vector<ll> totient(int n) {
    vector<bool> prime(n + 1, true);
    vector<ll> ans(n + 1);
    for (int i = 2; i <= n; i++) {
        ans[i] = i;
    }
    if (n >= 0) prime[0] = false;
    if (n >= 1) prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) {
            continue;
        }
        ans[i] *= i - 1;
        ans[i] /= i;
        for (int j = i + i; j <= n; j += i) {
            prime[j] = false;
            ans[j] *= i - 1;
            ans[j] /= i;
        }
    }
    return ans;
}

bool ispal(ll N) {
    string s = to_string(N);
    ll n = s.size();
    rep(i, n) {
        if (s[i] != s[n - 1 - i]) {
            return false;
        }
    }
    return true;
}





int main() {
	//cout << fixed << setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    ll N; cin >> N;
    ll p = N / 2;
    rep(i, p) {
        cout << '?' << " " << 2 * i << " " << 2 * i + 1 << endl;
        ll z; cin >> z;
        if (z == 2 * i ) {
            cout << "!" << " " << 2 * i + 1 << endl;
            return 0;
        }
        else if (z == 2 * i + 1) {
            cout << "!" << " " << 2 * i << endl;
            return 0;
        }
    }
    cout << "!" << " " << N - 1 << endl;
}
0