結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
|
提出日時 | 2019-09-01 05:51:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 864 bytes |
コンパイル時間 | 771 ms |
コンパイル使用メモリ | 77,728 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 06:36:01 |
合計ジャッジ時間 | 3,249 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 WA * 2 |
コンパイルメッセージ
main.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 8 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;int N;vector<int>A[2];int dp[3<<17];main(){cin>>N;dp[0]=0;for(int i=1;i<=N;i++)dp[i]=1e9;for(int i=0;i<N;i++){for(int j=1;i+j*j<=N;j++){dp[i+j*j]=min(dp[i+j*j],dp[i]+j);}}for(int i=1000;i;i--){while(i*i<=N&&dp[N-i*i]+i==dp[N]){N-=i*i;A[i%2].push_back(i);}}string ans="0";for(int i=0;i<2;i++)sort(A[i].begin(),A[i].end());for(int v:A[1]){ans+=ans[ans.size()-1];for(int i=2;i<=v;i++)ans+=ans[ans.size()-1]=='0'?'1':'0';}int L=0,R=(int)A[0].size()-1;while(L<=R){ans+=ans[ans.size()-1];for(int i=2;i<=A[0][R];i++)ans+=ans[ans.size()-1]=='0'?'1':'0';R--;if(L<=R){ans+=ans[ans.size()-1];for(int i=2;i<=A[0][L];i++)ans+=ans[ans.size()-1]=='0'?'1':'0';L++;}}cout<<ans.substr(1)<<endl;}