#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define N 2005
#define LOGN 20
#define int long long
int ans[N], dp[N][N];
pii root[N][N], to[N];
int c[N][N];
const int INF = 1e9 + 7;
string print(int i, int j)
{
if (i == 1 && j == 2)
{
return "0";
}
return print(root[i][j].st, root[i][j].nd) + (char)(c[i][j] + '0');
}
int32_t main()
{
//fileio();
fastio();
int t;
cin>>t;
memset(dp, INF, sizeof(dp));
memset(ans, INF, sizeof(ans));
dp[1][2] = 1;
for (int i = 1; i < N; i++)
{
for (int j = 2; j < N - i; j++)
{
if (dp[i + j][j] > dp[i][j] + 1)
{
root[i + j][j] = {i, j};
dp[i + j][j] = dp[i][j] + 1;
c[i + j][j] = 1;
}
if (dp[i][i + j] > dp[i][j] + 1)
{
dp[i][i + j] = dp[i][j] + 1;
root[i][i + j] = {i, j};
c[i][i + j] = 0;
}
if (ans[i + j - 2] > dp[i][j])
{
ans[i + j - 2] = dp[i][j];
to[i + j - 2] = {i, j};
}
}
}
for (int i = 1; i <= t; i++)
{
int k;
cin>>k;
cout<<-1<<endl;
string s = print(to[k].st, to[k].nd);
for (auto i : s)
cout<<i<<sp;
cout<<endl;
}
cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
102 ms |
126188 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
165 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
148 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
