結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
👑 ![]() |
提出日時 | 2019-08-30 23:16:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,131 bytes |
コンパイル時間 | 1,574 ms |
コンパイル使用メモリ | 120,500 KB |
最終ジャッジ日時 | 2025-01-07 16:05:16 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 WA * 1 |
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <chrono>#define _USE_MATH_DEFINES#include <cmath>#include <cstdio>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <iterator>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <string>#include <tuple>#include <utility>#include <vector>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()const int INF = 0x3f3f3f3f;const long long LINF = 0x3f3f3f3f3f3f3f3fLL;const double EPS = 1e-8;const int MOD = 1000000007; // 998244353;const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};/*-------------------------------------------------*/void solve(int len, char c, string &ans) {while (len--) {ans += c;if (c == '0') {c = '1';} else {c = '0';}}}int main() {cin.tie(0); ios::sync_with_stdio(false);// freopen("input.txt", "r", stdin);int n; cin >> n;vector<int> dp(n + 1, INF), prev(n + 1, -1);dp[0] = 0;FOR(i, 1, n + 1) {for (int j = 1; j * j <= i; ++j) {int score = dp[i - j * j] + j;if (score < dp[i]) {dp[i] = score;prev[i] = j;}}}vector<int> len_even, len_odd;int now = n;while (now > 0) {if (prev[now] % 2 == 0) {len_even.emplace_back(prev[now]);} else {len_odd.emplace_back(prev[now]);}now -= prev[now] * prev[now];}sort(ALL(len_odd));sort(ALL(len_even));string ans = "";for (int e : len_odd) solve(e, '0', ans);int l = 0, r = (int)len_even.size() - 1;if (len_odd.empty()) {solve(len_even[r], '0', ans);--r;if (l <= r) {solve(len_even[l], '1', ans);++l;}}while (l <= r) {solve(len_even[r], ans.back(), ans);--r;if (l <= r) {solve(len_even[l], ans.back(), ans);++l;}}cout << ans << '\n';return 0;}