結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2019-08-30 23:32:27 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,501 bytes |
コンパイル時間 | 717 ms |
コンパイル使用メモリ | 67,808 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 01:47:08 |
合計ジャッジ時間 | 2,880 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 WA * 2 |
ソースコード
#include <iostream>#include <utility>#include <algorithm>#include <queue>#include <vector>#define llint long longusing namespace std;llint n;llint dp[300005];int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;for(int i = 0; i <= n; i++) dp[i] = 1e9;dp[0] = 0;for(int i = 1; i <= n; i++){for(int j = 1; j*j <= i; j++){dp[i] = min(dp[i], dp[i-j*j]+j);}}//for(int i = 0; i <= n; i++) cout << i << " " << dp[i] << endl;vector<llint> vec;llint rem = n, cnt = dp[n];for(llint i = 1; i <= rem; i+=2){llint mx = 0;for(llint j = 1; i*i*j <= rem; j++){if(dp[rem-i*i*j] == cnt-i*j) mx = j;}for(llint j = 0; j < mx; j++) vec.push_back(i);rem -= mx*i*i, cnt -= mx*i;}for(llint i = (n+1)/2*2; i >= 2; i-=2){llint mx = 0;for(llint j = 1; i*i*j <= rem; j++){if(dp[rem-i*i*j] == cnt-i*j) mx = j;}for(llint j = 0; j < mx; j++) vec.push_back(i);rem -= mx*i*i, cnt -= mx*i;}vector<llint> ovec, evec;for(int i = 0; i < vec.size(); i++){if(vec[i]%2) ovec.push_back(vec[i]);else evec.push_back(vec[i]);}vec.clear();for(int i = 0; i < ovec.size(); i++) vec.push_back(ovec[i]);for(int i = 0; i < evec.size(); i++) vec.push_back(evec[i]);string ans;for(int i = 0; i < vec.size(); i++){for(int j = 0; j < vec[i]; j++) ans += ('0' + (i%2));}for(int i = 0; i < ans.size(); i++){if(i%2){if(ans[i] == '0') ans[i] = '1';else ans[i] = '0';}}cout << ans << endl;return 0;}