Submission #389355

#TimeUsernameProblemLanguageResultExecution timeMemory
389355Kevin_Zhang_TWBinary Subsequences (info1cup17_binary)C++17
82 / 100
1106 ms228432 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; } #else #define DE(...) 0 #define debug(...) 0 #endif const int MAX_N = 2010, MAX_W = 30, inf = MAX_N - 5, p = 1e9 + 7; ll hs(int a, int b) { if (a > b) swap(a, b); return 1000000ll * a + b; } unordered_map<ll, int> mp; int cal(int a, int b) { if (a + b <= 1) return a + b; if (a == b) return -1; if (a < b) swap(a, b); if (mp.count(hs(a, b))) return mp[hs(a, b)]; int need = a / (b + 1); int val = cal(a % (b + 1), b); if (val == -1) need = -1; else need += val; return mp[hs(a, b)] = need; } void gen(int a, int b) { vector<int> res; while (a + b) { if (a < b) { res.pb(1); b -= a + 1; } else { res.pb(0); a -= b + 1; } } for (int i = 0;i < res.size();++i) cout << res[i] << " \n"[i+1==res.size()]; } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); mp.reserve(10000003); int T; cin >> T; //#define BI(i) bitset<10>(i).to_string() while (T--) { int k; cin >> k; int cnt = 0; int need = inf, ind = -1; for (int i = 0;i <= k;++i) { int v = cal(i, k - i); if (v == -1) continue; if (chmin(need, v)) ind = i; ++cnt; } cout << cnt << '\n'; gen(ind, k - ind); } }

Compilation message (stderr)

binary.cpp: In function 'void gen(int, int)':
binary.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0;i < res.size();++i)
      |                 ~~^~~~~~~~~~~~
binary.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   cout << res[i] << " \n"[i+1==res.size()];
      |                           ~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...