結果
問題 | No.2608 Divide into two |
ユーザー |
|
提出日時 | 2024-01-19 22:19:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,119 bytes |
コンパイル時間 | 22,497 ms |
コンパイル使用メモリ | 356,852 KB |
最終ジャッジ日時 | 2025-02-18 21:13:51 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | AC * 1 WA * 1 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;using ll=long long;void IO(){ios::sync_with_stdio(false);std::cin.tie(nullptr);}int main(){IO();ll t;cin>>t;while(t--){ll n;cin>>n;vector<ll> a(n);for(ll i=0;i<n;i++){a[i]=i+1;}vector<ll> b(n,0);vector<vector<bool>> dp(n+1,vector<bool>(n*(n+1)/4+1,false));dp[0][0]=true;for(ll i=0;i<n;i++){for(ll j=0;j<=n*(n+1)/4;j++){if(j+a[i]<=n*(n+1)/4&&dp[i][j]){dp[i+1][j+a[i]]=true;}if(j+b[i]<=n*(n+1)/4&&dp[i][j]){dp[i+1][j+b[i]]=true;}}}if(!dp[n][n*(n+1)/4]){cout<<-1<<endl;}else{string ans;ll now=n*(n+1)/4;for(ll i=n;i>=1;i--){if(dp[i-1][now-a[i-1]]){now-=a[i-1];ans+='0';}else{now-=b[i-1];ans+='1';}}reverse(ans.begin(),ans.end());cout<<ans<<endl;}}}