結果

問題 No.2608 Divide into two
コンテスト
ユーザー yel
提出日時 2024-01-19 21:42:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 174 ms / 1,000 ms
コード長 1,579 bytes
コンパイル時間 2,934 ms
コンパイル使用メモリ 251,704 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-28 04:13:53
合計ジャッジ時間 3,546 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

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