Submission #1139242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139242		Agageldi	Binary Subsequences (info1cup17_binary)	C++20	0 / 100	1096 ms	2296 KiB

binary

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 600005
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sz(s) (int)s.size()

ll T, n, a[N], t, ans,b[25];
string s;
map <string,int> vis;
void solve(int x) {
	if(x == sz(s) + 1) {
		string g = "";
		for(int i = 1; i <= sz(s); i++) {
			if(b[i]) g+=s[i-1];
		}
		if(sz(g) > 0){
			sort(all(g));
			if(!vis[g]) {
				vis[g] = 1;
				ans++;
			}
		}
		return;
	}
	for(int i = 0; i <= 1; i++) {
		b[x] = i;
		solve(x + 1);
	}
}

int main () {
	cin >> T;
	while(T--) {
		cin >> n;
		string answer = "";
		for(int i = 1;i<=n;i++) {
			answer += '1';
		}
		for(int i = 1; i <= 12; i++) {
			vis.clear();
			s = "";
			int tt = i;
			while(tt > 0) {
				s += '1';
				tt--;
			}
			ans = 0;
			memset(b,0,sizeof b);
			vis.clear();
			solve(1);
			if(ans == n && s < answer) {
				answer = s;
			}
			if(ans > n) break;
			for(int j = 1; j <= 12; j++) {
				s += '0';
				ans = 0;
				vis.clear();
				memset(b, 0,sizeof b);
				solve(1);
				if(ans == n && s < answer) {
					answer = s;
				}
				if(ans > n) break;
			}
		}
		cout << "-1\n";
		for(int i = 0;i< sz(answer);i++) {
			cout << answer[i]<<" ";
		}
		cout << '\n';
	}
}

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