結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2019-09-01 17:50:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,104 bytes |
コンパイル時間 | 2,239 ms |
コンパイル使用メモリ | 175,316 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 06:38:19 |
合計ジャッジ時間 | 3,709 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 WA * 1 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;#define F first#define S second#define pii pair<int, int>#define eb emplace_back#define all(v) v.begin(), v.end()#define rep(i, n) for (int i = 0; i < (n); ++i)#define rep3(i, l, n) for (int i = l; i < (n); ++i)#define sz(v) (int)v.size()#define inf (int)(1e9+7)#define abs(x) (x >= 0 ? x : -(x))#define ceil(a, b) a / b + !!(a % b)ll pow(ll a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }int main() {int n;cin >> n;const int MAX_N = 300001;int dp[MAX_N];rep(i, MAX_N) dp[i] = inf;dp[0] = 0;dp[1] = 1;int from[MAX_N];fill_n(from, MAX_N, -1);from[1] = 1;rep3(i, 2, n + 1) for (int j = 1; j * j <= i; ++j) {if (dp[i] > dp[i - j * j] + j) {dp[i] = dp[i - j * j] + j;from[i] = j * j;}}// rep(i, n + 1) cout << dp[i] << " "; cout << endl;// rep(i, n + 1) cout << from[i] << " "; cout << endl;vector<int> o, e;{int now = n;int tmp = sqrt(from[now]);if (tmp % 2) o.eb(tmp);else e.eb(tmp);while (1) {now -= from[now];if (from[now] == -1) break;tmp = sqrt(from[now]);if (tmp % 2) o.eb(tmp);else e.eb(tmp);}}sort(e.rbegin(), e.rend());vector<int> e2;int turn = (sz(e) + 1) / 2;rep(i, turn) {e2.eb(e[i]);int b = sz(e) - 1 - i;if (i != b) e2.eb(e[b]);}// rep(i, sz(e2)) cout << e2[i] << " "; cout << endl;n = sz(o) + sz(e);string str;rep(i, sz(o)) {int now = 0;rep(j, o[i]) {str += now + '0';now ^= 1;}}rep(i, sz(e2)) {int now = (sz(str) ? str.back() - '0' : 0);rep(j, e2[i]) {str += now + '0';now ^= 1;}}cout << str << endl;}