Submission #349007

#	Time	Username	Problem	Language	Result	Execution time	Memory
349007		RohamIzadidoost	Binary Subsequences (info1cup17_binary)	C++14	30.10 / 100	79 ms	2156 KiB

binary

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 1000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 18 ; 
ll dp[lg + 10][2]  , ans[maxn]; 
string s; 
string to(int x){
	string res ; 
	while(x >= 0){
	//	cout<<"x : " << x <<" : " << char( (int)'0' + x & 1 )  << endl ; 
		res += char( '0' + (x & 1) ) ; 
		x /= 2 ;
		if(x == 0) break ; 
	}
	res += '#' ; 
	reverse(all(res)) ; 
	return res ; 
}
ll cal(int x){
	s = to(x) ; 
//	cout<<x <<" : " << s << endl ; 
	for(int i = 1 ; i < sz(s) ; i ++ ){
		dp[i][0] = dp[i][1] = 0 ; 
		dp[i][s[i] - '0'] ++ ; 
		dp[i][0] += dp[i-1][0] ;
		dp[i][1] += dp[i-1][1] ;
		if(s[i] == '1'){
			dp[i][1] += dp[i-1][0] ; 
		}else dp[i][0] += dp[i-1][1] ; 
	}
	return dp[sz(s) - 1][0] + dp[sz(s) - 1][1] ; 
}
int main()
{
	migmig ;
	memset(ans , -1 , sizeof ans) ;
	for(int i = 0 ; i < (1 << lg) ; i ++ ){
		int x = cal(i) ; 
		if(x > 2000)continue ; 
		if(ans[x] == -1) ans[x] = i ; 
	}
	int t , k; 
	cin>>t ; 
	while(t--){
		cin>>k ; 
		cout<<-1 << endl ; 
		if(ans[k] == -1){
			cout<<-1 << endl;
		}else{
			s = to(ans[k]) ;
			for(int i = 1 ; i < sz(s) ; i ++ ) cout<<s[i] <<" " ; 
			cout<<endl ;  
		}
	}	
}

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