Submission #405357

#	Time	Username	Problem	Language	Result	Execution time	Memory
405357		Falcon	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3206 ms	93312 KiB

subsequence

#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;
array<int, 1 << B> popcnt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    rep(i, 1 << B) popcnt[i] = __builtin_popcount(i);


    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);
    
    vector<int> len(n, 1), pre(n, -1);
    rep(i, n) {
        {
        int tail = a[i] & ((1 << B) - 1);
        rep(x, 1 << B) {
            int req = k[i] - popcnt[(a[i] >> B) & x];
            if(req >= 0 && req <= B) {
                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][popcnt[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:58:5: note: in expansion of macro 'debug'
   58 |     debug(n, a, k);
      |     ^~~~~
subsequence.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
subsequence.cpp:77:5: note: in expansion of macro 'debug'
   77 |     debug(len, pre);
      |     ^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60