Submission #603291

#	Time	Username	Problem	Language	Result	Execution time	Memory
603291		izanbf	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	41 ms	90976 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;
const int mask_r = (1<<10) - 1;
const int mask_l = mask_r << 10;
// dp[prefix][sufix][num] : length of the largest beautiful sequence ending
//                          in a value with left bits equal to <prefix>, and 
//                          having <num> common right bits with <sufix> 
int dp[1<<10][1<<10][11];
int jp[1<<10][1<<10][11];
int previ[MAXN];
int a[MAXN];
int k[MAXN];

inline int left_bits(int v)  {  return (v & mask_l) >> 10;    }
inline int right_bits(int v) {  return v & mask_r;            }
inline int bitcount(int v)   {  return __builtin_popcount(v); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n) {
        memset(dp, 0, sizeof(dp));
        memset(jp, 0xff, sizeof(jp));
        memset(previ, 0xff, sizeof(previ));

        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> k[i];

        int ans = -1;
        int last = -1;

        for (int i = 0; i < n; ++i) {
            int longest = 0;

            for (int pref = 0; pref < (1<<10); ++pref) {
                int common_left = bitcount(pref & left_bits(a[i]));
                int required_common_right = k[i] - common_left;
                if (required_common_right >= 0) {
                    int length = 1 + dp[pref][right_bits(a[i])][required_common_right];
                    if (length > longest) {
                        longest = length;
                        previ[i] = jp[pref][right_bits(a[i])][required_common_right];
                    }
                }
            }

            for (int suf = 0; suf < (1<<10); ++suf) {
                int& length = dp[left_bits(a[i])][suf][bitcount(right_bits(a[i]) & suf)];
                if (length < longest) {
                    length = longest;
                    jp[left_bits(a[i])][suf][bitcount(right_bits(a[i]) & suf)] = i;
                }
            }
            
            if (longest > ans) {
                ans = longest;
                last = i;
            }
        }

        vector<int> seq;
        while (last != -1) {
            seq.push_back(last);
            last = previ[last];
        }
        reverse(seq.begin(), seq.end());

        cout << seq.size() << endl;
        for (int i = 0; i < seq.size(); ++i) {
            if (i > 0) cout << ' ';
            cout << 1+seq[i];
        }
        cout << endl;
    }
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 0; i < seq.size(); ++i) {
      |                         ~~^~~~~~~~~~~~

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