Submission #67784

#TimeUsernameProblemLanguageResultExecution timeMemory
67784cdemirerBinary Subsequences (info1cup17_binary)C++17
0 / 100
112 ms816 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ii> vii; typedef vector<vii> vvii; typedef pair<double, double> dodo; #define mp(x, y) make_pair(x, y) #define pb(x) push_back(x) #define LIM (2000) int N; int tcs[2000]; vi ans1; vii ans2; void precalc() { ans1.resize(LIM+1); ans2.resize(LIM+1); fill(ans2.begin(), ans2.end(), mp(-1, -1)); for (int m = 0; m < (1<<20)-1; m++) { //int m = 0; int last1val = 0, last0val = 0; int total = 0; int pm = 0; for (int i = 0; i < 20; i++) { //cerr << "DBG" << " " << m << " " << i << " " << total << endl; //cerr << "m&asdas: " << (m & (1<<i)) << endl; pm |= (m & (1<<i)); int val = total + 1; bool type = m & (1<<i); if (type) { val -= last1val; last1val += val; } else { val -= last0val; last0val += val; } //cerr << val << endl; total += val; if (total > LIM) break; if (pm == m) { //cerr << ": " << total << endl; ans1[total]++; if (ans2[total] == mp(-1, -1) || i < ans2[total].second) ans2[total] = mp(pm, i); } } } } void solve12() { precalc(); //cerr << "DBG" << endl; for (int i = 0; i < N; i++) { //cout << tcs[i] << " "; cout << ans1[ tcs[i] ] << '\n'; for (int k = 0; k <= ans2[ tcs[i] ].second; k++) { cout << (bool)( ans2[ tcs[i] ].first & (1<<k) ) << " "; } cout << '\n'; } //cerr << "DBG" << endl; } int main(int argc, char **argv) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 0; i < N; i++) cin >> tcs[i]; if (all_of(tcs, tcs+N, [](int x){return x <= 100000;})) solve12(); else exit(-1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...