Submission #649433

#	Time	Username	Problem	Language	Result	Execution time	Memory
649433		dozer	Binary Subsequences (info1cup17_binary)	C++14	30.10 / 100	165 ms	262144 KiB

binary

#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";
}

• Subtask 1: 30.1 / 43
• Subtask 2: 0 / 39
• Subtask 3: 0 / 18