Submission #692263

#	Time	Username	Problem	Language	Result	Execution time	Memory
692263		Nhoksocqt1	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2043 ms	51944 KiB

subsequence

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;
const int MAXV = 1 << 20;

int dp[MAXN], f[1 << 10][1 << 10][11], cntBit[MAXV];
int val[MAXN], eq[MAXN], nArr;

int magicFunc(void) {
    for (int mask = 0; mask < (1 << 20); ++mask)
        cntBit[mask] = __builtin_popcount(mask);

    for (int mask = 0; mask < (1 << 10); ++mask)
        f[mask][0][0] = 0;

    int res(0);
    for (int i = 1; i <= nArr; ++i) {
        dp[i] = 1;
        int pre = val[i] >> 10, suf = val[i] & ((1 << 10) - 1);
        for (int j = 0; j < (1 << 10); ++j) {
            int b = cntBit[j & pre];
            if(b > eq[i] || eq[i] - b > 10)
                continue;

            dp[i] = max(dp[i], 1 + f[j][suf][eq[i] - b]);
        }

        for (int j = 0; j < (1 << 10); ++j) {
            int b = cntBit[j & suf];
            f[pre][j][b] = max(f[pre][j][b], dp[i]);
        }

        res = max(res, dp[i]);
    }

    return res;
}

void traceAnswer(void) {
    int pos(0);
    for (int i = 1; i <= nArr; ++i) {
        if(dp[pos] < dp[i])
            pos = i;
    }

    stack<int> st;
    st.push(pos);

    for (int i = pos - 1; i > 0; --i) {
        if(dp[i] == dp[pos] - 1 && __builtin_popcount(val[i] & val[pos]) == eq[pos]) {
            pos = i;
            st.push(pos);
        }
    }

    while(st.size()) {
        cout << st.top() << ' ';
        st.pop();
    }

    cout << '\n';
}

void process() {
    cin >> nArr;
    for (int i = 1; i <= nArr; ++i) {
        cin >> val[i];
    }

    for (int i = 1; i <= nArr; ++i) {
        cin >> eq[i];
    }
  
    cout << magicFunc() << '\n';
    traceAnswer();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("ATHM.inp", "r", stdin);
//    freopen("ATHM.out", "w", stdout);

    process();
    return 0;
}

Compilation message (stderr)

subsequence.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
subsequence.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

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