結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:00:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 2,478 bytes |
コンパイル時間 | 925 ms |
コンパイル使用メモリ | 111,656 KB |
実行使用メモリ | 23,680 KB |
最終ジャッジ日時 | 2024-06-11 13:57:35 |
合計ジャッジ時間 | 3,719 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<cassert>using namespace std;//#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;const ll mod = 1000000007;const ll INF = mod * mod;typedef pair<int, int> P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef pair<ll, ll> LP;typedef vector<ll> vec;typedef long double ld;typedef pair<ld, ld> LDP;const ld eps = 1e-5;bool chked[300001];int leng[300001];int lengdfs(int n) {if (n == 0)return 0;if (chked[n])return leng[n];chked[n] = true;int ret = mod;rep1(j, n) {if (j*j > n)break;ret = min(ret, j + lengdfs(n - j * j));}return leng[n] = ret;}void solve() {int n; cin >> n;int cur = lengdfs(n);string ans;int id = 0;while (n > 0) {bool ansed = false;for (int i = 1; i <= n; i+=2) {if (n - i * i < 0)break;int sum = i + leng[n - i * i];//cout << cur << " " << sum << endl;if (sum == cur) {rep(j, i) {if (j % 2 == 0)ans.push_back('0');else ans.push_back('1');}n -= i * i; cur -= i;ansed = true;break;}}if (!ansed)break;}while (n > 0) {if (id == 0) {int k = sqrt(n + 1); k = (k / 2) * 2 + 2;for (int i = k; i >= 2; i -= 2) {if (n - i * i < 0)continue;int sum = i + leng[n - i * i];if (sum == cur) {rep(j, i) {if (j % 2 == 0)ans.push_back('0');else ans.push_back('1');}n -= i * i; cur -= i;break;}}}else {for (int i = 2; i <= n; i += 2) {if (n - i * i < 0)break;int sum = i + leng[n - i * i];if (sum == cur) {rep(j, i) {if (j % 2 == 0)ans.push_back('1');else ans.push_back('0');}n -= i * i; cur -= i;break;}}}id ^= 1;}cout << ans << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(5);//init();solve();//cout << "finish" << endl;//stopreturn 0;}