結果
| 問題 | No.1306 Exactly 2 Digits |
| ユーザー |
 torisasami4
|
| 提出日時 | 2020-12-04 14:12:04 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 151 ms / 2,000 ms |
| コード長 | 10,796 bytes |
| コンパイル時間 | 2,031 ms |
| コンパイル使用メモリ | 179,656 KB |
| 実行使用メモリ | 51,624 KB |
| 平均クエリ数 | 1237.78 |
| 最終ジャッジ日時 | 2024-07-17 09:27:43 |
| 合計ジャッジ時間 | 17,055 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 123 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:469:43: warning: 'ma' may be used uninitialized [-Wmaybe-uninitialized]
469 | ans[1] = -mi + n * (n - 1 - ma);
| ~~~~~~~^~~~~
main.cpp:447:23: note: 'ma' was declared here
447 | int mi = 1e9, ma, s = 1e9, e, f;
| ^~
main.cpp:468:9: warning: 'f' may be used uninitialized [-Wmaybe-uninitialized]
468 | if(f){ // miが1の位
| ^~
main.cpp:447:39: note: 'f' was declared here
447 | int mi = 1e9, ma, s = 1e9, e, f;
| ^
main.cpp:470:24: warning: 't' may be used uninitialized [-Wmaybe-uninitialized]
470 | ans[t] = n * (n - 1);
| ~~~~~~~^~~~~~~~~~~~~
main.cpp:464:13: note: 't' was declared here
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;elsef = 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]);elseans[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]);elseans[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]);elseans[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]);elseans[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;}