Submission #62250

#TimeUsernameProblemLanguageResultExecution timeMemory
62250BenqBinary Subsequences (info1cup17_binary)C++11
82 / 100
1075 ms736 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 100001; bool ok[10][10]; void brute() { ok[0][0] = 1; F0R(i,10) { F0R(j,10) { // cout << ok[i][j]; if (ok[i][j]) cout << i << " " << j << "\n"; if (ok[i][j] && i+j+1 < 10) ok[i+j+1][j] = ok[i][i+j+1] = 1; } cout << "\n"; } } int K; int get(int a, int b) { // a >= b if (a == b) { if (a != 1) return MOD; return 0; } int mul = (a-1)/b; return mul+get(b,a-mul*b); } void GET(int l, int r) { if (l == r) return; if (l > r) { int mul = (l-1)/r; GET(l-mul*r,r); F0R(i,mul) cout << "0 "; } else { int mul = (r-1)/l; GET(l,r-mul*l); F0R(i,mul) cout << "1 "; } } void solve() { cin >> K; int ans = 0; pi bes = {MOD,MOD}; F0R(i,K+1) { int x = get(max(i+1,K-i+1),min(i+1,K-i+1)); bes = min(bes,{x,i}); if (x < MOD) ans ++; } cout << ans << "\n"; GET(bes.s+1,K-bes.s+1); cout << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; F0R(i,T) solve(); } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...