Submission #405345

#TimeUsernameProblemLanguageResultExecution timeMemory
405345FalconLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6078 ms93220 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it) #define rep(i, N) for(int i = 0; i < (N); ++i) #define rrep(i, N) for(int i = (N) - 1; i >= 0; --i) #define rep1(i, N) for(int i = 1; i <= (N); ++i) #define rep2(i, s, e) for(int i = (s); i <= (e); ++i) #ifdef DEBUG #define debug(x...) { \ ++dbg::depth; \ string dbg_vals = dbg::to_string(x); \ --dbg::depth; \ dbg::fprint(__func__, __LINE__, #x, dbg_vals); \ } #define light_debug(x) { \ dbg::light = true; \ dbg::dout << __func__ << ":" << __LINE__; \ dbg::dout << " " << #x << " = " << x << endl; \ dbg::light = false; \ } #else #define debug(x...) 42 #define light_debug(x) 42 #endif using ll = long long; template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } constexpr int B = 10; array<array<array<pair<int, int>, B + 1>, 1 << B>, 1 << B> dp; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n), k(n); rep(i, n) cin >> a[i]; rep(i, n) cin >> k[i]; debug(n, a, k); for(auto& x: dp) for(auto& y: x) for(auto& z: y) z = {0, -1}; vector<int> len(n, 1), pre(n, -1); rep(i, n) { debug(i); rep(x, 1 << B) { int req = k[i] - __builtin_popcount((a[i] >> B) & x); int tail = a[i] & ((1 << B) - 1); if(req >= 0 && req <= B && ~dp[x][tail][req].first) { if(len[i] < 1 + dp[x][tail][req].first) tie(len[i], pre[i]) = dp[x][tail][req], ++len[i]; } } rep(tail, 1 << B) { ckmax(dp[a[i] >> B][tail][__builtin_popcount(a[i] & tail)], {len[i], i}); } } debug(len, pre); int ans_i = int(max_element(all(len)) - len.begin()); cout << len[ans_i] << '\n'; vector<int> ans; ans.reserve(len[ans_i]); for(; ~ans_i; ans_i = pre[ans_i]) ans.push_back(ans_i); rrep(i, int(ans.size())) cout << ans[i] + 1 << ' '; cout << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl; #endif return 0; }

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
subsequence.cpp:56:5: note: in expansion of macro 'debug'
   56 |     debug(n, a, k);
      |     ^~~~~
subsequence.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
subsequence.cpp:62:9: note: in expansion of macro 'debug'
   62 |         debug(i);
      |         ^~~~~
subsequence.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
subsequence.cpp:76:5: note: in expansion of macro 'debug'
   76 |     debug(len, pre);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...