結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2025-04-20 10:52:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 3,153 bytes |
コンパイル時間 | 2,162 ms |
コンパイル使用メモリ | 198,308 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-04-20 10:52:09 |
合計ジャッジ時間 | 3,176 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
// Problem: No.3 ビットすごろく // Contest: yukicoder // URL: https://yukicoder.me/problems/11 // Memory Limit: 512 MB // Time Limit: 5000 ms // // Powered by CP Editor (https://cpeditor.org) //By: OIer rui_er #include <bits/stdc++.h> #define rep(x, y, z) for(int x = (y); x <= (z); ++x) #define per(x, y, z) for(int x = (y); x >= (z); --x) #define debug(format...) fprintf(stderr, format) #define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false) #define endl '\n' using namespace std; typedef long long ll; mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count()); int randint(int L, int R) { uniform_int_distribution<int> dist(L, R); return dist(rnd); } template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;} template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;} template<int mod> inline unsigned int down(unsigned int x) { return x >= mod ? x - mod : x; } template<int mod> struct Modint { unsigned int x; Modint() = default; Modint(unsigned int x) : x(x) {} friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;} friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;} friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);} friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);} friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;} friend Modint operator/(Modint a, Modint b) {return a * ~b;} friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;} friend Modint operator~(Modint a) {return a ^ (mod - 2);} friend Modint operator-(Modint a) {return down<mod>(mod - a.x);} friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;} friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;} friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;} friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;} friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;} friend Modint& operator++(Modint& a) {return a += 1;} friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;} friend Modint& operator--(Modint& a) {return a -= 1;} friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;} friend bool operator==(Modint a, Modint b) {return a.x == b.x;} friend bool operator!=(Modint a, Modint b) {return !(a == b);} }; const int N = 1e4 + 5, inf = 0x3f3f3f3f; int n, f[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; memset(f, 0x3f, sizeof(f)); queue<int> q; f[1] = 1; q.push(1); while(!q.empty()) { int u = q.front(); q.pop(); int d = __builtin_popcount(u); if(u - d >= 1 && f[u - d] == +inf) { f[u - d] = f[u] + 1; q.push(u - d); } if(u + d <= n && f[u + d] == +inf) { f[u + d] = f[u] + 1; q.push(u + d); } } cout << (f[n] == +inf ? -1 : f[n]) << endl; return 0; }