結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2019-08-31 16:16:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,224 bytes |
コンパイル時間 | 1,728 ms |
コンパイル使用メモリ | 167,384 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-06-24 19:29:35 |
合計ジャッジ時間 | 4,106 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 WA * 1 |
ソースコード
#include<bits/stdc++.h>#define int long longusing namespace std;#define rep(i, n) for(int i=0;i<(n);++i)typedef pair<int, int> pii;const int INF = 1l << 60;#define u_b upper_bound#define l_b lower_boundint dp[300300];int minv[300300];int maxv[300300];bool les(int a, int b) {if (a % 2 != b % 2) {return a % 2;}if (a % 2 == 1) {return a < b;}return a > b;}signed main() {int N;cin >> N;fill(dp, dp + 300300, INF);dp[0] = 0;minv[0] = 0, maxv[0] = 0;for (int i = 1; i <= N; ++i) {for (int j = 1; i - j * j >= 0; ++j) {if (dp[i] > dp[i - j * j] + j) {dp[i] = dp[i - j * j] + j;minv[i] = j;maxv[i] = j;} else if (dp[i] == dp[i - j * j] + j) {minv[i] = les(minv[i], j) ? minv[i] : j;maxv[i] = les(maxv[i], j) ? j : maxv[j];}}}string ans;int s = 0;while (N) {int j = s == 0 ? minv[N] : maxv[N];rep(i, j) {ans.push_back(s + '0');s = 1 - s;}s = 1 - s;N -= j * j;}cout << ans << endl;return 0;}