結果

問題 No.2608 Divide into two
ユーザー yelyel
提出日時 2024-01-19 21:42:20
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 173 ms / 1,000 ms
コード長 1,579 bytes
コンパイル時間 4,199 ms
コンパイル使用メモリ 252,672 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-01-19 21:42:25
合計ジャッジ時間 3,735 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 24 ms
6,676 KB
testcase_02 AC 173 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
//using mint = modint998244353;
//using mint = modint1000000007;
typedef long long ll;
typedef unsigned long long ull;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int MAX = 1e9;
const int MIN = -1*1e9;
const ll MAXLL = 1e18;
const ll MINLL = -1*1e18;
//const ll MOD = 998244353;
//const ll MOD = 1000000007;

int main()
{   
    int T; cin >> T;
    for(int t = 0; t < T; t++)
    {
        int N; cin >> N;
        if(((1+N)*N/2)%2!=0)
        {
            cout << -1 << endl;
            continue;
        }

        vector<vector<int>> DP(N+1,vector<int>((1+N)*N/2));
        DP[0][0] = true;
        for(int i = 1; i <= N; i++)
        {
            for(int j = 0; j <= (1+N)*N/4; j++)
            {
                if(DP[i-1][j])
                {
                    DP[i][j] = true;
                    if(j+i > (1+N)*N/4) continue;
                    DP[i][j+i] = true;
                }
            }
        }
        if(!DP[N][(1+N)*N/4]) cout << "-1" << endl;
        else
        {
            string Ans;
            int Pos = (1+N)*N/4;
            for(int i = N; i >= 1; i--)
            {
                if(DP[i-1][Pos])
                {
                    Ans += "0";
                }
                else
                {
                    Ans += "1";
                    Pos -= i;
                }
            }
            reverse(all(Ans));
            cout << Ans << endl;
        }   
    }
    return 0;
}
0