結果
問題 | No.2753 鳩の巣原理 |
ユーザー | NAMIDAIRO |
提出日時 | 2024-05-11 01:40:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,529 bytes |
コンパイル時間 | 1,291 ms |
コンパイル使用メモリ | 115,368 KB |
実行使用メモリ | 25,580 KB |
平均クエリ数 | 11.00 |
最終ジャッジ日時 | 2024-05-11 01:40:34 |
合計ジャッジ時間 | 4,702 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
24,580 KB |
testcase_01 | AC | 19 ms
25,220 KB |
testcase_02 | AC | 20 ms
24,836 KB |
testcase_03 | AC | 21 ms
24,964 KB |
testcase_04 | AC | 22 ms
24,836 KB |
testcase_05 | AC | 21 ms
24,580 KB |
testcase_06 | AC | 20 ms
24,580 KB |
testcase_07 | AC | 22 ms
24,964 KB |
testcase_08 | AC | 21 ms
24,964 KB |
testcase_09 | AC | 25 ms
24,812 KB |
testcase_10 | AC | 20 ms
25,196 KB |
testcase_11 | WA | - |
testcase_12 | AC | 22 ms
24,940 KB |
testcase_13 | WA | - |
testcase_14 | AC | 24 ms
25,180 KB |
testcase_15 | AC | 20 ms
24,556 KB |
testcase_16 | AC | 19 ms
25,196 KB |
testcase_17 | AC | 21 ms
24,800 KB |
testcase_18 | AC | 22 ms
24,812 KB |
testcase_19 | AC | 25 ms
25,196 KB |
testcase_20 | AC | 21 ms
24,812 KB |
testcase_21 | AC | 20 ms
25,196 KB |
testcase_22 | AC | 21 ms
24,812 KB |
testcase_23 | AC | 20 ms
24,800 KB |
testcase_24 | AC | 21 ms
24,940 KB |
testcase_25 | AC | 20 ms
24,796 KB |
testcase_26 | AC | 22 ms
24,940 KB |
testcase_27 | AC | 22 ms
24,812 KB |
testcase_28 | AC | 21 ms
25,196 KB |
testcase_29 | AC | 21 ms
25,196 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <set> #include <random> #include <iomanip> #include <string> #include <cmath> #include <complex> using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (n); i++) template<class T> using vi = vector<T>; template<class T> using vii = vector<vi<T>>; template<class T> using viii = vector<vii<T>>; template<class T> using viiii = vector<viii<T>>; using P = pair<ll, int>; void chmin(ll & x, ll y) { x = min(x, y); } void chmax(ll& x, ll y) { x = max(x, y); } struct mint { const long long mod = 998244353; long long x; mint(long long x_ = 0) : x((x_% mod + mod) % mod) {} mint& operator+=(const mint& other) { x += other.x; if (x >= mod) x -= mod; return *this; } mint& operator-=(const mint& other) { x -= other.x; if (x < 0) x += mod; return *this; } mint& operator*=(const mint& other) { x *= other.x; x %= mod; return *this; } mint& operator+=(const long long n) { return *this += mint(n); } mint& operator-=(const long long n) { return *this -= mint(n); } mint& operator*=(const long long n) { return *this *= mint(n); } mint& operator=(const mint& other) { x = other.x; return *this; } mint& operator=(const long long n) { x = n % mod; return *this; } bool operator==(const mint& other) const { return x == other.x; } bool operator!=(const mint& other) const { return x != other.x; } mint operator-() const { mint res(mod - x); return res; } mint operator+(const mint& other) const { mint res(x); return res += other; } mint operator-(const mint& other) const { mint res(x); return res -= other; } mint operator*(const mint& other) const { mint res(x); return res *= other; } mint operator+(const long long n) const { mint res(x); mint other(n); return res += other; } mint operator-(const long long n) const { mint res(x); mint other(n); return res -= other; } mint operator*(const long long n) const { mint res(x); mint other(n); return res *= other; } mint pow(long long n) const { if (n == 0) return mint(1); mint res = pow(n / 2); res *= res; if (n % 2) res *= *this; return res; } mint inv() const { return pow(mod - 2); } mint& operator/=(const mint& other) { *this *= other.inv(); return *this; } mint operator/(const mint& other) const { mint res(x); return res /= other; } }; struct combination { vector<mint> fact, ifact; combination(int m) :fact(m + 1), ifact(m + 1) { fact[0] = 1; for (int i = 1; i <= m; i++) fact[i] = fact[i - 1] * mint(i); ifact[m] = fact[m].inv(); for (int i = m; i >= 1; i--) ifact[i - 1] = ifact[i] * mint(i); } mint operator()(int n, int k) {//for n<=m, calc nck if (k < 0 || k > n) return mint(0); return fact[n] * ifact[k] * ifact[n - k]; } }; template<class T> struct NTT { const int divlim = 23; //when mod is 998244353 vector<mint> root, invroot; const mint primitive = 3; NTT() : root(divlim + 1), invroot(divlim + 1) { root[divlim] = primitive.pow((primitive.mod - 1) >> divlim); invroot[divlim] = root[divlim].inv(); for (int i = divlim - 1; i >= 0; i--) { root[i] = root[i + 1] * root[i + 1]; invroot[i] = invroot[i + 1] * invroot[i + 1]; } } void dft(vector<mint>& d, const int log, const bool inv = false) { int n = (int)d.size(); if (n == 1 || log == 0) return; vector<mint> d0, d1; for (int i = 0; i < n / 2; i++) { d0.push_back(d[2 * i]); d1.push_back(d[2 * i + 1]); } dft(d0, log - 1, inv); dft(d1, log - 1, inv); mint pow = 1, z = (inv ? invroot[log] : root[log]); for (int i = 0; i < n / 2; i++) { d[i] = d0[i] + d1[i] * pow; pow *= z; } for (int i = n / 2; i < n; i++) { d[i] = d0[i - n / 2] + d1[i - n / 2] * pow; pow *= z; } return; } void idft(vector<mint>& d, const int log) { dft(d, log, true); return; } vector<mint> convolution(vector<T>& f, vector<T>& g) { int n = 1, log = 0, lenf = (int)f.size(), leng = (int)g.size(); while (n < lenf + leng) { n <<= 1; log++; } vector<mint> df(n), dg(n); for (int i = 0; i < lenf; i++) df[i] = f[i]; for (int i = 0; i < leng; i++) dg[i] = g[i]; dft(df, log); dft(dg, log); for (int i = 0; i < n; i++) df[i] *= dg[i]; idft(df, log); mint ninv = mint(n).inv(); for (int i = 0; i < n; i++) df[i] *= ninv; return df; } }; int main() { int n; cin >> n; int ok = 1, ng = n; rep(i, 10) { int mid = (ok + ng) / 2; cout << "? " << mid << endl; int pg; cin >> pg; if (pg == mid) ok = mid; else ng = mid; } cout << "Yes "; cout << ok << " " << ok + 1 << endl; return 0; }