結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:01:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 2,804 bytes |
コンパイル時間 | 2,993 ms |
コンパイル使用メモリ | 212,668 KB |
最終ジャッジ日時 | 2025-01-07 15:53:10 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;inline void rd(int &x){int k, m=0;x=0;for(;;){k = getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline void wt_L(char a){putchar_unlocked(a);}inline void wt_L(const char c[]){int i=0;for(i=0;c[i]!='\0';i++){putchar_unlocked(c[i]);}}template<class S, class T> inline S chmin(S &a, T b){if(a>b){a=b;}return a;}int N;int dp[300001];char res[300001];int ress;int search(int mode){int i;if(mode==0){for(i=1;i*i<=N;i+=2){if(dp[N] == dp[N-i*i] + i){return i;}}for(i=2;i*i<=N;i+=2){;}for(;;){i -= 2;if(dp[N] == dp[N-i*i] + i){return i;}}}else{for(i=2;i*i<=N;i+=2){if(dp[N] == dp[N-i*i] + i){return i;}}for(i=1;i*i<=N;i+=2){;}for(;;){i -= 2;if(dp[N] == dp[N-i*i] + i){return i;}}}return -1;}int main(){int i, j, k, s;for(i=0;i<(300001);i++){dp[i] = 1073709056;}dp[0] = 0;for(i=1;i*i<=300000;i++){for(j=i*i;j<=300000;j++){chmin(dp[j], dp[j-i*i] + i);}}rd(N);while(N){if(ress==0 || res[ress-1] == 0){s = 0;}else{s = 1;}i = search(s);N -= i * i;for(j=0;j<(i);j++){res[ress++] = (s+j)%2;}}for(i=0;i<(ress);i++){res[i] += '0';}wt_L(res);wt_L('\n');return 0;}// cLay varsion 20190830-1// --- original code ---// int N;// int dp[300001];//// char res[300001]; int ress;//// int search(int mode){// int i;//// if(mode==0){// for(i=1;i*i<=N;i+=2){// if(dp[N] == dp[N-i*i] + i) return i;// }//// for(i=2;i*i<=N;i+=2);// for(;;){// i -= 2;// if(dp[N] == dp[N-i*i] + i) return i;// }// } else {// for(i=2;i*i<=N;i+=2){// if(dp[N] == dp[N-i*i] + i) return i;// }//// for(i=1;i*i<=N;i+=2);// for(;;){// i -= 2;// if(dp[N] == dp[N-i*i] + i) return i;// }// }//// return -1;// }//// {// int i, j, k, s;//// rep(i,300001) dp[i] = int_inf;// dp[0] = 0;//// for(i=1;i*i<=300000;i++){// for(j=i*i;j<=300000;j++) dp[j] <?= dp[j-i*i] + i;// }//// rd(N);// while(N){// if(ress==0 || res[ress-1] == 0) s = 0;// else s = 1;// i = search(s);// N -= i * i;// rep(j,i) res[ress++] = (s+j)%2;// }//// rep(i,ress) res[i] += '0';// wt(res);// }