結果
| 問題 | No.2870 Dice Making |
| ユーザー |
 fuppy_kyopro
|
| 提出日時 | 2024-09-06 21:22:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 13,425 bytes |
| コンパイル時間 | 2,554 ms |
| コンパイル使用メモリ | 209,848 KB |
| 最終ジャッジ日時 | 2025-02-24 03:58:01 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
/*#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")//*/// #include <atcoder/all>// #include <atcoder/segtree>#include <bits/stdc++.h>using namespace std;// using namespace atcoder;// #define _GLIBCXX_DEBUG#define DEBUG(x) cerr << #x << ": " << x << endl;#define DEBUG_VEC(v) \cerr << #v << ":"; \for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \cerr << " " << v[iiiiiiii]; \cerr << endl;#define DEBUG_MAT(v) \cerr << #v << endl; \for (int iv = 0; iv < v.size(); iv++) { \for (int jv = 0; jv < v[iv].size(); jv++) { \cerr << v[iv][jv] << " "; \} \cerr << endl; \}typedef long long ll;// #define int ll#define vi vector<int>#define vl vector<ll>#define vii vector<vector<int>>#define vll vector<vector<ll>>#define pii pair<int, int>#define pis pair<int, string>#define psi pair<string, int>#define pll pair<ll, ll>template <class S, class T>pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {return pair<S, T>(s.first + t.first, s.second + t.second);}template <class S, class T>pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }template <class S, class T>ostream &operator<<(ostream &os, pair<S, T> p) {os << "(" << p.first << ", " << p.second << ")";return os;}#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; i--)#define rrep1(i, n) for (int i = (int)(n); i > 0; i--)#define REP(i, a, b) for (int i = a; i < b; i++)#define in(x, a, b) (a <= x && x < b)#define all(c) c.begin(), c.end()void YES(bool t = true) {cout << (t ? "YES" : "NO") << endl;}void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; }void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; }void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; }void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; }void no(bool t = true) { cout << (t ? "no" : "yes") << endl; }template <class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return 1;}return 0;}template <class T>bool chmin(T &a, const T &b) {if (a > b) {a = b;return 1;}return 0;}template <class T, class U>T ceil_div(T a, U b) {return (a + b - 1) / b;}template <class T>T safe_mul(T a, T b) {if (a == 0 || b == 0) return 0;if (numeric_limits<T>::max() / a < b) return numeric_limits<T>::max();return a * b;}#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());const ll inf = 1000000001;const ll INF = (ll)1e18 + 1;const long double pi = 3.1415926535897932384626433832795028841971L;int popcount(ll t) { return __builtin_popcountll(t); }vector<int> gen_perm(int n) {vector<int> ret(n);iota(all(ret), 0);return ret;}// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };vi dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0};vi dx2 = {1, 1, 0, -1, -1, -1, 0, 1}, dy2 = {0, 1, 1, 1, 0, -1, -1, -1};struct Setup_io {Setup_io() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(25);cerr << fixed << setprecision(25);}} setup_io;// constexpr ll MOD = 1000000007;constexpr ll MOD = 998244353;// #define mp make_pair// https://judge.yosupo.jp/submission/55343// noimi のライブラリを窃盗したnamespace inner {using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;template <typename T>T gcd(T a, T b) {while (b)swap(a %= b, b);return a;}uint64_t gcd_impl(uint64_t n, uint64_t m) {constexpr uint64_t K = 5;for (int i = 0; i < 80; ++i) {uint64_t t = n - m;uint64_t s = n - m * K;bool q = t < m;bool p = t < m * K;n = q ? m : t;m = q ? t : m;if (m == 0) return n;n = p ? n : s;}return gcd_impl(m, n % m);}uint64_t gcd_pre(uint64_t n, uint64_t m) {for (int i = 0; i < 4; ++i) {uint64_t t = n - m;bool q = t < m;n = q ? m : t;m = q ? t : m;if (m == 0) return n;}return gcd_impl(n, m);}uint64_t gcd_fast(uint64_t n, uint64_t m) { return n > m ? gcd_pre(n, m) : gcd_pre(m, n); }template <typename T = int32_t>T inv(T a, T p) {T b = p, x = 1, y = 0;while (a) {T q = b % a;swap(a, b /= a);swap(x, y -= q * x);}assert(b == 1);return y < 0 ? y + p : y;}template <typename T = int32_t, typename U = int64_t>T modpow(T a, U n, T p) {T ret = 1;for (; n; n >>= 1, a = U(a) * a % p)if (n & 1) ret = U(ret) * a % p;return ret;}} // namespace innerunsigned long long rng() {static unsigned long long x_ = 88172645463325252ULL;x_ = x_ ^ (x_ << 7);return x_ = x_ ^ (x_ >> 9);}using namespace std;struct ArbitraryLazyMontgomeryModInt {using mint = ArbitraryLazyMontgomeryModInt;using i32 = int32_t;using u32 = uint32_t;using u64 = uint64_t;static u32 mod;static u32 r;static u32 n2;static u32 get_r() {u32 ret = mod;for (i32 i = 0; i < 4; ++i)ret *= 2 - mod * ret;return ret;}static void set_mod(u32 m) {assert(m < (1 << 30));assert((m & 1) == 1);mod = m;n2 = -u64(m) % m;r = get_r();assert(r * mod == 1);}u32 a;ArbitraryLazyMontgomeryModInt() : a(0) {}ArbitraryLazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){};static u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * mod) >> 32; }mint &operator+=(const mint &b) {if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;return *this;}mint &operator-=(const mint &b) {if (i32(a -= b.a) < 0) a += 2 * mod;return *this;}mint &operator*=(const mint &b) {a = reduce(u64(a) * b.a);return *this;}mint &operator/=(const mint &b) {*this *= b.inverse();return *this;}mint operator+(const mint &b) const { return mint(*this) += b; }mint operator-(const mint &b) const { return mint(*this) -= b; }mint operator*(const mint &b) const { return mint(*this) *= b; }mint operator/(const mint &b) const { return mint(*this) /= b; }bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); }bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); }mint operator-() const { return mint() - mint(*this); }mint pow(u64 n) const {mint ret(1), mul(*this);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); }friend istream &operator>>(istream &is, mint &b) {int64_t t;is >> t;b = ArbitraryLazyMontgomeryModInt(t);return (is);}mint inverse() const { return pow(mod - 2); }u32 get() const {u32 ret = reduce(a);return ret >= mod ? ret - mod : ret;}static u32 get_mod() { return mod; }};typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::mod;typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::r;typename ArbitraryLazyMontgomeryModInt::u32 ArbitraryLazyMontgomeryModInt::n2;using namespace std;struct montgomery64 {using mint = montgomery64;using i64 = int64_t;using u64 = uint64_t;using u128 = __uint128_t;static u64 mod;static u64 r;static u64 n2;static u64 get_r() {u64 ret = mod;for (i64 i = 0; i < 5; ++i)ret *= 2 - mod * ret;return ret;}static void set_mod(u64 m) {assert(m < (1LL << 62));assert((m & 1) == 1);mod = m;n2 = -u128(m) % m;r = get_r();assert(r * mod == 1);}u64 a;montgomery64() : a(0) {}montgomery64(const int64_t &b) : a(reduce((u128(b) + mod) * n2)){};static u64 reduce(const u128 &b) { return (b + u128(u64(b) * u64(-r)) * mod) >> 64; }mint &operator+=(const mint &b) {if (i64(a += b.a - 2 * mod) < 0) a += 2 * mod;return *this;}mint &operator-=(const mint &b) {if (i64(a -= b.a) < 0) a += 2 * mod;return *this;}mint &operator*=(const mint &b) {a = reduce(u128(a) * b.a);return *this;}mint &operator/=(const mint &b) {*this *= b.inverse();return *this;}mint operator+(const mint &b) const { return mint(*this) += b; }mint operator-(const mint &b) const { return mint(*this) -= b; }mint operator*(const mint &b) const { return mint(*this) *= b; }mint operator/(const mint &b) const { return mint(*this) /= b; }bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); }bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); }mint operator-() const { return mint() - mint(*this); }mint pow(u128 n) const {mint ret(1), mul(*this);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); }friend istream &operator>>(istream &is, mint &b) {int64_t t;is >> t;b = montgomery64(t);return (is);}mint inverse() const { return pow(mod - 2); }u64 get() const {u64 ret = reduce(a);return ret >= mod ? ret - mod : ret;}static u64 get_mod() { return mod; }};typename montgomery64::u64 montgomery64::mod, montgomery64::r, montgomery64::n2;namespace fast_factorize {using u64 = uint64_t;template <typename mint>bool miller_rabin(u64 n, vector<u64> as) {if (mint::get_mod() != n) mint::set_mod(n);u64 d = n - 1;while (~d & 1)d >>= 1;mint e{1}, rev{int64_t(n - 1)};for (u64 a : as) {if (n <= a) break;u64 t = d;mint y = mint(a).pow(t);while (t != n - 1 && y != e && y != rev) {y *= y;t *= 2;}if (y != rev && t % 2 == 0) return false;}return true;}bool is_prime(u64 n) {if (~n & 1) return n == 2;if (n <= 1) return false;if (n < (1LL << 30))return miller_rabin<ArbitraryLazyMontgomeryModInt>(n, {2, 7, 61});elsereturn miller_rabin<montgomery64>(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});}template <typename mint, typename T>T pollard_rho(T n) {if (~n & 1) return 2;if (is_prime(n)) return n;if (mint::get_mod() != n) mint::set_mod(n);mint R, one = 1;auto f = [&](mint x) { return x * x + R; };auto rnd = [&]() { return rng() % (n - 2) + 2; };while (1) {mint x, y, ys, q = one;R = rnd(), y = rnd();T g = 1;constexpr int m = 128;for (int r = 1; g == 1; r <<= 1) {x = y;for (int i = 0; i < r; ++i)y = f(y);for (int k = 0; g == 1 && k < r; k += m) {ys = y;for (int i = 0; i < m && i < r - k; ++i)q *= x - (y = f(y));g = inner::gcd_fast(q.get(), n);}}if (g == n) dog = inner::gcd_fast((x - (ys = f(ys))).get(), n);while (g == 1);if (g != n) return g;}exit(1);}vector<u64> inner_factorize(u64 n) {if (n <= 1) return {};u64 p;if (n <= (1LL << 30))p = pollard_rho<ArbitraryLazyMontgomeryModInt>(n);elsep = pollard_rho<montgomery64>(n);if (p == n) return {p};auto l = inner_factorize(p);auto r = inner_factorize(n / p);copy(begin(r), end(r), back_inserter(l));return l;}vector<u64> factorize(u64 n) {auto ret = inner_factorize(n);sort(begin(ret), end(ret));return ret;}} // namespace fast_factorizeusing fast_factorize::factorize;using fast_factorize::is_prime;signed main() {int n, k;cin >> n >> k;if (n == 1) {if (k == 1) {cout << 1 << endl;} else {cout << -1 << endl;}return 0;}for (int m = 1; m <= n; m++) {if (n % m == 0 && n / m == k) {rep(i, m) {cout << 1 << " ";}rep(i, n - m) {cout << 2 << " ";}cout << endl;return 0;}}cout << -1 << endl;}