結果
問題 | No.2748 Strange Clock |
ユーザー |
![]() |
提出日時 | 2024-04-20 16:31:12 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,661 bytes |
コンパイル時間 | 2,416 ms |
コンパイル使用メモリ | 222,020 KB |
実行使用メモリ | 144,768 KB |
最終ジャッジ日時 | 2024-10-12 12:19:12 |
合計ジャッジ時間 | 9,868 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 4 WA * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define FOR(i, l, r) for(ll i = l; i < r; i++) #define rep(i, n) FOR(i, 0, n) #define FORR(i, l, r) for(ll i = r - 1; i >= l; i--) #define ALL(ar) begin(ar), end(ar) template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << p.first << ' ' << p.second; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for(T &x : v) is >> x; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for(size_t i = 0; i < v.size(); i++) os << (i ? " " : "") << v[i]; return os; } //------------------------------------------------- // 返り値: a と b の最大公約数 // ax + by = gcd(a, b) を満たす (x, y) が格納される 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; } ll po(ll x, ll n) { ll res = 1; rep(i, n) res *= x; return res; } ll p2[16], p3[16], p4[16], p6[16]; void solve() { rep(i, 16) { p2[i] = po(2, i); p3[i] = po(3, i); p4[i] = po(4, i); p6[i] = po(6, i); } ll n, m; cin >> n >> m; m += 3; if(n == 1) { if(m <= 12) { cout << 1 << endl; } else { cout << 0 << endl; } return; } if(n == 2) { if(m <= 144) { cout << 3 << endl; } else { cout << 0 << endl; } return; } vector<int> d(n); map<pair<ll, ll>, vector<pair<ll, ll>>> mp; rep(i, po(3, n - 2)) { ll d1 = 0, d2 = 0; ll sum3 = 0, sum4 = 0; rep(j, n) { d1 += (p6[j] - p3[j]) * d[j]; d2 += (p6[j] - p4[j]) * d[j]; sum3 += p3[j] * d[j]; sum4 += p4[j] * d[j]; } d1 %= p3[n]; d2 %= p2[n]; mp[{d1, d2}].emplace_back(sum3, sum4); d[2]++; rep(j, n) if(d[j] == 3) { d[j] = 0; if(j + 1 < n) d[j + 1]++; } } int ans = 0; const ll p12 = po(12, n); ll x, y; extGCD(p3[n], p4[n], x, y); x %= p4[n]; y %= p3[n]; while(y > 0) { y -= p3[n]; x += p4[n]; } cout << x << " " << y << endl; for(const auto &[key, vec] : mp) { if(vec.size() == 1) { if(m <= p12) ans++; } else { vector<ll> t; for(auto [l, r] : vec) { ll tmp = l - vec[0].first; if(r - l >= vec[0].second - vec[0].first) { tmp += x * ((r - l) - (vec[0].second - vec[0].first)) % p4[n] * p3[n]; } else { tmp += (x - p4[n]) * ((r - l) - (vec[0].second - vec[0].first)) % p4[n] * p3[n]; } t.push_back(tmp); } t.push_back(p12); sort(ALL(t)); rep(i, t.size() - 1) if(m <= t[i + 1] - t[i]) ans++; } } cout << ans * 3 << endl; } int main() { int t = 1; // cin >> t; while(t--) solve(); }