#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
using pii = pair<int,int>;
#define fs first
#define sc second
int cnt[2010] = {0};
int dp[2010][2010]; // dp[目前dp值][上一個0] = 上一個1
pii lst[2010][2010];
int len[2010][2010] = {0};
char cc[2010][2010];
string s[2010];
queue<int> q[2010];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
for (int i = 0; i <= 2005; i++) for (int j = 0; j <= 2005; j++) dp[i][j] = 888888, len[i][j] = 114514;
dp[1][0] = 0;
len[1][0] = 0;
q[1].push(0);
for (int i = 1; i <= 2005; i++) {
while (q[i].size()) {
int lst0 = q[i].front(); q[i].pop();
int lst1 = dp[i][lst0];
{ // 接 0
int ni = i*2 - lst0;
if (ni <= 2005) {
cnt[ni]++;
int n0 = i, n1 = lst1;
q[ni].push(n0);
cc[ni][n0] = '0';
dp[ni][n0] = n1;
lst[ni][n0] = make_pair(i,lst0);
len[ni][n0] = len[i][lst0] + 1;
}
}
{ // 接 0
int ni = i*2 - lst1;
if (ni <= 2005) {
cnt[ni]++;
int n0 = lst0, n1 = i;
q[ni].push(n0);
cc[ni][n0] = '1';
dp[ni][n0] = n1;
lst[ni][n0] = make_pair(i,lst0);
len[ni][n0] = len[i][lst0] + 1;
}
}
}
}
int t;
cin >> t;
while (t--) {
int k;
cin >> k;
k++;
cout << cnt[k] << '\n';
int ansid = 0;
for (int i = 0; i <= 2005; i++) if (len[k][i] < len[k][ansid]) ansid = i;
vector<char> ans;
pii me = {k, ansid};
while (me != make_pair(1,0)) {
ans.push_back(cc[me.fs][me.sc]);
me = lst[me.fs][me.sc];
}
reverse(ans.begin(), ans.end());
for (char c : ans) cout << c << ' '; cout << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |