結果
問題 | No.1306 Exactly 2 Digits |
ユーザー | torisasami4 |
提出日時 | 2020-12-04 14:12:04 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 10,796 bytes |
コンパイル時間 | 1,885 ms |
コンパイル使用メモリ | 176,872 KB |
実行使用メモリ | 50,632 KB |
平均クエリ数 | 1237.78 |
最終ジャッジ日時 | 2023-09-24 08:59:37 |
合計ジャッジ時間 | 17,170 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
50,120 KB |
testcase_01 | AC | 35 ms
50,040 KB |
testcase_02 | AC | 35 ms
50,140 KB |
testcase_03 | AC | 36 ms
50,192 KB |
testcase_04 | AC | 34 ms
50,060 KB |
testcase_05 | AC | 35 ms
50,140 KB |
testcase_06 | AC | 34 ms
50,292 KB |
testcase_07 | AC | 34 ms
49,956 KB |
testcase_08 | AC | 34 ms
49,940 KB |
testcase_09 | AC | 35 ms
50,332 KB |
testcase_10 | AC | 35 ms
49,940 KB |
testcase_11 | AC | 35 ms
49,840 KB |
testcase_12 | AC | 33 ms
50,404 KB |
testcase_13 | AC | 35 ms
49,920 KB |
testcase_14 | AC | 34 ms
49,832 KB |
testcase_15 | AC | 36 ms
50,104 KB |
testcase_16 | AC | 34 ms
50,380 KB |
testcase_17 | AC | 35 ms
50,336 KB |
testcase_18 | AC | 35 ms
50,200 KB |
testcase_19 | AC | 34 ms
49,928 KB |
testcase_20 | AC | 35 ms
50,044 KB |
testcase_21 | AC | 34 ms
50,480 KB |
testcase_22 | AC | 35 ms
50,416 KB |
testcase_23 | AC | 34 ms
49,948 KB |
testcase_24 | AC | 36 ms
50,204 KB |
testcase_25 | AC | 35 ms
50,368 KB |
testcase_26 | AC | 34 ms
50,540 KB |
testcase_27 | AC | 35 ms
50,100 KB |
testcase_28 | AC | 36 ms
49,972 KB |
testcase_29 | AC | 36 ms
49,844 KB |
testcase_30 | AC | 37 ms
50,268 KB |
testcase_31 | AC | 36 ms
49,716 KB |
testcase_32 | AC | 35 ms
50,388 KB |
testcase_33 | AC | 36 ms
50,352 KB |
testcase_34 | AC | 35 ms
49,912 KB |
testcase_35 | AC | 36 ms
50,520 KB |
testcase_36 | AC | 35 ms
49,748 KB |
testcase_37 | AC | 36 ms
50,180 KB |
testcase_38 | AC | 37 ms
49,956 KB |
testcase_39 | AC | 36 ms
49,880 KB |
testcase_40 | AC | 37 ms
50,156 KB |
testcase_41 | AC | 36 ms
50,180 KB |
testcase_42 | AC | 37 ms
50,112 KB |
testcase_43 | AC | 35 ms
49,792 KB |
testcase_44 | AC | 39 ms
50,268 KB |
testcase_45 | AC | 38 ms
50,108 KB |
testcase_46 | AC | 38 ms
50,036 KB |
testcase_47 | AC | 38 ms
50,220 KB |
testcase_48 | AC | 39 ms
50,344 KB |
testcase_49 | AC | 41 ms
50,052 KB |
testcase_50 | AC | 41 ms
50,100 KB |
testcase_51 | AC | 42 ms
49,828 KB |
testcase_52 | AC | 44 ms
50,000 KB |
testcase_53 | AC | 48 ms
50,328 KB |
testcase_54 | AC | 45 ms
50,116 KB |
testcase_55 | AC | 47 ms
50,324 KB |
testcase_56 | AC | 50 ms
49,824 KB |
testcase_57 | AC | 51 ms
50,200 KB |
testcase_58 | AC | 52 ms
50,356 KB |
testcase_59 | AC | 51 ms
50,256 KB |
testcase_60 | AC | 58 ms
49,824 KB |
testcase_61 | AC | 62 ms
50,256 KB |
testcase_62 | AC | 62 ms
50,248 KB |
testcase_63 | AC | 65 ms
50,184 KB |
testcase_64 | AC | 62 ms
49,900 KB |
testcase_65 | AC | 66 ms
49,984 KB |
testcase_66 | AC | 71 ms
50,352 KB |
testcase_67 | AC | 73 ms
50,356 KB |
testcase_68 | AC | 72 ms
50,116 KB |
testcase_69 | AC | 77 ms
50,260 KB |
testcase_70 | AC | 77 ms
50,336 KB |
testcase_71 | AC | 82 ms
49,924 KB |
testcase_72 | AC | 82 ms
50,516 KB |
testcase_73 | AC | 79 ms
49,836 KB |
testcase_74 | AC | 90 ms
50,084 KB |
testcase_75 | AC | 88 ms
49,892 KB |
testcase_76 | AC | 97 ms
50,340 KB |
testcase_77 | AC | 104 ms
50,000 KB |
testcase_78 | AC | 111 ms
50,424 KB |
testcase_79 | AC | 121 ms
49,816 KB |
testcase_80 | AC | 123 ms
49,884 KB |
testcase_81 | AC | 101 ms
49,864 KB |
testcase_82 | AC | 125 ms
49,956 KB |
testcase_83 | AC | 128 ms
50,592 KB |
testcase_84 | AC | 138 ms
50,200 KB |
testcase_85 | AC | 144 ms
50,056 KB |
testcase_86 | AC | 123 ms
49,900 KB |
testcase_87 | AC | 125 ms
50,248 KB |
testcase_88 | AC | 154 ms
49,860 KB |
testcase_89 | AC | 131 ms
50,060 KB |
testcase_90 | AC | 116 ms
50,064 KB |
testcase_91 | AC | 126 ms
49,868 KB |
testcase_92 | AC | 116 ms
49,836 KB |
testcase_93 | AC | 136 ms
50,556 KB |
testcase_94 | AC | 116 ms
49,996 KB |
testcase_95 | AC | 122 ms
50,440 KB |
testcase_96 | AC | 113 ms
49,948 KB |
testcase_97 | AC | 112 ms
50,180 KB |
testcase_98 | AC | 109 ms
50,048 KB |
testcase_99 | AC | 124 ms
49,972 KB |
testcase_100 | AC | 124 ms
50,160 KB |
testcase_101 | AC | 136 ms
49,788 KB |
testcase_102 | AC | 116 ms
49,984 KB |
testcase_103 | AC | 120 ms
50,444 KB |
testcase_104 | AC | 121 ms
50,632 KB |
testcase_105 | AC | 122 ms
50,320 KB |
testcase_106 | AC | 109 ms
49,852 KB |
testcase_107 | AC | 125 ms
49,840 KB |
testcase_108 | AC | 116 ms
50,000 KB |
testcase_109 | AC | 139 ms
50,112 KB |
testcase_110 | AC | 114 ms
50,156 KB |
testcase_111 | AC | 118 ms
49,828 KB |
testcase_112 | AC | 106 ms
50,580 KB |
testcase_113 | AC | 144 ms
49,828 KB |
testcase_114 | AC | 147 ms
50,436 KB |
testcase_115 | AC | 124 ms
50,004 KB |
testcase_116 | AC | 151 ms
50,284 KB |
testcase_117 | AC | 127 ms
50,224 KB |
testcase_118 | AC | 136 ms
50,028 KB |
testcase_119 | AC | 119 ms
49,824 KB |
testcase_120 | AC | 109 ms
50,060 KB |
testcase_121 | AC | 129 ms
50,520 KB |
testcase_122 | AC | 128 ms
49,916 KB |
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内: main.cpp:469:43: 警告: ‘ma’ may be used uninitialized [-Wmaybe-uninitialized] 469 | ans[1] = -mi + n * (n - 1 - ma); | ~~~~~~~^~~~~ main.cpp:447:23: 備考: ‘ma’ はここで定義されています 447 | int mi = 1e9, ma, s = 1e9, e, f; | ^~ main.cpp:468:9: 警告: ‘f’ may be used uninitialized [-Wmaybe-uninitialized] 468 | if(f){ // miが1の位 | ^~ main.cpp:447:39: 備考: ‘f’ はここで定義されています 447 | int mi = 1e9, ma, s = 1e9, e, f; | ^ main.cpp:470:24: 警告: ‘t’ may be used uninitialized [-Wmaybe-uninitialized] 470 | ans[t] = n * (n - 1); | ~~~~~~~^~~~~~~~~~~~~ main.cpp:464:13: 備考: ‘t’ はここで定義されています 464 | int t, p2, q2; | ^
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb(x) push_back(x) #define mp(a, b) make_pair(a, b) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define lscan(x) scanf("%I64d", &x) #define lprint(x) printf("%I64d", x) #define rep(i, n) for (ll i = 0; i < (n); i++) #define rep2(i, n) for (ll i = n - 1; i >= 0; i--) template <class T> using rque = priority_queue<T, vector<T>, greater<T>>; const ll mod = 998244353; ll gcd(ll a, ll b) { ll c = a % b; while (c != 0) { a = b; b = c; c = a % b; } return b; } long long extGCD(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } struct UnionFind { vector<ll> data; UnionFind(int sz) { data.assign(sz, -1); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return (false); if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return (true); } int find(int k) { if (data[k] < 0) return (k); return (data[k] = find(data[k])); } ll size(int k) { return (-data[find(k)]); } }; ll M = 1000000007; vector<ll> fac(2000011); //n!(mod M) vector<ll> ifac(2000011); //k!^{M-2} (mod M) ll mpow(ll x, ll n) { ll ans = 1; while (n != 0) { if (n & 1) ans = ans * x % M; x = x * x % M; n = n >> 1; } return ans; } ll mpow2(ll x, ll n, ll mod) { ll ans = 1; while (n != 0) { if (n & 1) ans = ans * x % mod; x = x * x % mod; n = n >> 1; } return ans; } void setcomb() { fac[0] = 1; ifac[0] = 1; for (ll i = 0; i < 2000010; i++) { fac[i + 1] = fac[i] * (i + 1) % M; // n!(mod M) } ifac[2000010] = mpow(fac[2000010], M - 2); for (ll i = 2000010; i > 0; i--) { ifac[i - 1] = ifac[i] * i % M; } } ll comb(ll a, ll b) { if (a == 0 && b == 0) return 1; if (a < b || a < 0) return 0; ll tmp = ifac[a - b] * ifac[b] % M; return tmp * fac[a] % M; } ll perm(ll a, ll b) { if (a == 0 && b == 0) return 1; if (a < b || a < 0) return 0; return fac[a] * ifac[a - b] % M; } long long modinv(long long a) { long long b = M, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= M; if (u < 0) u += M; return u; } ll modinv2(ll a, ll mod) { ll b = mod, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } template <int mod> struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt &operator+=(const ModInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt<mod>(t); return (is); } static int get_mod() { return mod; } }; using mint = ModInt<mod>; typedef vector<vector<mint>> Matrix; Matrix mul(Matrix a, Matrix b) { assert(a[0].size() == b.size()); int i, j, k; int n = a.size(), m = b[0].size(), l = a[0].size(); Matrix c(n, vector<mint>(m)); for (i = 0; i < n; i++) for (k = 0; k < l; k++) for (j = 0; j < m; j++) c[i][j] += a[i][k] * b[k][j]; return c; } Matrix mat_pow(Matrix x, ll n) { ll k = x.size(); Matrix ans(k, vector<mint>(k, 0)); for (int i = 0; i < k; i++) ans[i][i] = 1; while (n != 0) { if (n & 1) ans = mul(ans, x); x = mul(x, x); n = n >> 1; } return ans; } template <int mod> struct NumberTheoreticTransform { vector<int> rev, rts; int base, max_base, root; NumberTheoreticTransform() : base(1), rev{0, 1}, rts{0, 1} { assert(mod >= 3 && mod % 2 == 1); auto tmp = mod - 1; max_base = 0; while (tmp % 2 == 0) tmp >>= 1, max_base++; root = 2; while (mod_pow(root, (mod - 1) >> 1) == 1) ++root; assert(mod_pow(root, mod - 1) == 1); root = mod_pow(root, (mod - 1) >> max_base); } inline int mod_pow(int x, int n) { int ret = 1; while (n > 0) { if (n & 1) ret = mul(ret, x); x = mul(x, x); n >>= 1; } return ret; } inline int inverse(int x) { return mod_pow(x, mod - 2); } inline unsigned add(unsigned x, unsigned y) { x += y; if (x >= mod) x -= mod; return x; } inline unsigned mul(unsigned a, unsigned b) { return 1ull * a * b % (unsigned long long)mod; } void ensure_base(int nbase) { if (nbase <= base) return; rev.resize(1 << nbase); rts.resize(1 << nbase); for (int i = 0; i < (1 << nbase); i++) { rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1)); } assert(nbase <= max_base); while (base < nbase) { int z = mod_pow(root, 1 << (max_base - 1 - base)); for (int i = 1 << (base - 1); i < (1 << base); i++) { rts[i << 1] = rts[i]; rts[(i << 1) + 1] = mul(rts[i], z); } ++base; } } void ntt(vector<int> &a) { const int n = (int)a.size(); assert((n & (n - 1)) == 0); int zeros = __builtin_ctz(n); ensure_base(zeros); int shift = base - zeros; for (int i = 0; i < n; i++) { if (i < (rev[i] >> shift)) { swap(a[i], a[rev[i] >> shift]); } } for (int k = 1; k < n; k <<= 1) { for (int i = 0; i < n; i += 2 * k) { for (int j = 0; j < k; j++) { int z = mul(a[i + j + k], rts[j + k]); a[i + j + k] = add(a[i + j], mod - z); a[i + j] = add(a[i + j], z); } } } } vector<int> multiply(vector<int> a, vector<int> b) { int need = a.size() + b.size() - 1; int nbase = 1; while ((1 << nbase) < need) nbase++; ensure_base(nbase); int sz = 1 << nbase; a.resize(sz, 0); b.resize(sz, 0); ntt(a); ntt(b); int inv_sz = inverse(sz); for (int i = 0; i < sz; i++) { a[i] = mul(a[i], mul(b[i], inv_sz)); } reverse(a.begin() + 1, a.end()); ntt(a); a.resize(need); return a; } vector<int> pol_pow(vector<int> a, ll n) { vector<int> ans(1, 1); int k = a.size(); while (n != 0) { if (n & 1){ ans = multiply(ans, a); ans.resize(k); } a = multiply(a, a); a.resize(k); n = n >> 1; } return ans; } }; int main() { int n; cin>>n; int cnt[3 * n] = {}, p[n*n-n+10], q[n*n-n+10]; for (int i = 1; i <= n * n - n; i++){ cout << "? " << i << " 1" << endl; cin >> p[i] >> q[i]; cnt[p[i]+n]++, cnt[q[i]+n]++; } int ans[n * n - n + 10]; rep(i, n * n - n + 10) ans[i] = -1; int mi = 1e9, ma, s = 1e9, e, f; rep(i,3*n){ if(cnt[i]&&mi>1e8){ mi = i - n; if(cnt[i] == n-1) f = 1; else f = 0; } if(cnt[i] == 2*n-1){ e = i - n; if(s>1e8) s = i - n; } if(cnt[i]) ma = i - n; } int t, p2, q2; for (int i = 1; i <= n * n - n; i++) if(p[i]==mi&&q[i]==ma) t = i; if(f){ // miが1の位 ans[1] = -mi + n * (n - 1 - ma); ans[t] = n * (n - 1); for (int i = 1; i <= n * n - n; i++){ if(ans[i] == -1){ if(cnt[p[i] + n] != 2*n-1){ if(cnt[p[i] + n] == n-1) ans[i] = (ans[1] % n + p[i]) + n * (ans[1] / n + q[i]); else ans[i] = (ans[1] % n + q[i]) + n * (ans[1] / n + p[i]); } else if(cnt[q[i] + n] != 2*n-1){ if(cnt[q[i] + n] == n) ans[i] = (ans[1] % n + p[i]) + n * (ans[1] / n + q[i]); else ans[i] = (ans[1] % n + q[i]) + n * (ans[1] / n + p[i]); } else if(p[i] == q[i]){ ans[i] = (ans[1] % n + p[i]) + n * (ans[1] / n + q[i]); } else{ cout << "? " << i << " " << t << endl; cin >> p2 >> q2; ans[i] = n * (n - 1 + p2) + q2; for (int j = i + 1; j <= n * n - n; j++){ if(p[i]==p[j]&&q[i]==q[j]){ ans[j] = n * (ans[1] / n + ans[i] % n - ans[1] % n) + (ans[1] % n + ans[i] / n - ans[1] / n); break; } } } } } } else{ // miがnの位 ans[1] = n * (1 - mi) + (n - 1 - ma); ans[t] = 2 * n - 1; for (int i = 1; i <= n * n - n; i++){ if(ans[i] == -1){ if(cnt[p[i] + n] != 2*n-1){ if(cnt[p[i] + n] == n-1) ans[i] = (ans[1] % n + p[i]) + n * (ans[1] / n + q[i]); else ans[i] = (ans[1] % n + q[i]) + n * (ans[1] / n + p[i]); } else if(cnt[q[i] + n] != 2*n-1){ if(cnt[q[i] + n] == n) ans[i] = (ans[1] % n + p[i]) + n * (ans[1] / n + q[i]); else ans[i] = (ans[1] % n + q[i]) + n * (ans[1] / n + p[i]); } else if(p[i] == q[i]){ ans[i] = (ans[1] % n + p[i]) + n * (ans[1] / n + q[i]); } else{ cout << "? " << i << " " << t << endl; cin >> p2 >> q2; ans[i] = n * (q2 + 1) + (n - 1 + p2); for (int j = i + 1; j <= n * n - n; j++){ if(p[i]==p[j]&&q[i]==q[j]){ ans[j] = n * (ans[1] / n + ans[i] % n - ans[1] % n) + (ans[1] % n + ans[i] / n - ans[1] / n); break; } } } } } } cout << "!"; for (int i = 1; i <= n * n - n; i++) cout << " " << ans[i]; cout << endl; }