Submission #679068

#	Time	Username	Problem	Language	Result	Execution time	Memory
679068		grandmast3r	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3889 ms	126284 KiB

subsequence

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2", "popcnt")

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef ON_PC
        freopen("input.txt", "r", stdin);
    #endif
    // freopen("output.txt", "w", stdout);
    int T = 1;
    // cin >> T;
    while (T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++){
            cin >> a[i];
        }
        vector<int> k(n + 1);
        for (int i = 1; i <= n; i++){
            cin >> k[i];
        }
        vector<int> dp(n + 1, 1);
        vector<int> pr(n + 1);
        vector<vector<vector<pair<int, int>>>> mx((1 << 10), vector<vector<pair<int, int>>>((1 << 10), vector<pair<int, int>>(11, {-1, -1})));
        for (int i = 1; i <= n; i++){
            int p = (a[i] >> 10);
            int q = (a[i] & ((1 << 10) - 1));
            for (int x = 0; x < (1 << 10); x++){
                int cur = __builtin_popcount((x << 10) & a[i]);
                if (k[i] - cur >= 0 && k[i] - cur <= 10){
                    pair<int, int> qq = mx[x][q][k[i] - cur];
                    if (qq.second != -1 && qq.first + 1 > dp[i]){
                        dp[i] = qq.first + 1;
                        pr[i] = qq.second;
                    }
                }
            }
            for (int y = 0; y < (1 << 10); y++){
                int cnt = __builtin_popcount(q & y);
                mx[p][y][cnt] = max(mx[p][y][cnt], {dp[i], i});
            }
        }
        int v = 1;
        for (int i = 1; i <= n; i++){
            if (dp[i] > dp[v]){
                v = i;
            }
        }
        vector<int> res;
        while (v){
            res.push_back(v);
            v = pr[v];
        }
        reverse(all(res));
        cout << res.size() << "\n";
        for (int i = 0; i < res.size(); i++){
            cout << res[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}

Compilation message (stderr)

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

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