Submission #485835

#	Time	Username	Problem	Language	Result	Execution time	Memory
485835		XII	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2040 ms	48272 KiB

subsequence

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

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IZhO17_subsequence"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 1e5 + 1;
int a[N], b[N], n;
const int M = 10;
int cnt[1 << M];
int dp[1 << M][1 << M][M + 1];
int f[N], t[N];

int main(){
    IOS;
    Fi();
    cin >> n;
    FORU(i, 1, n) cin >> a[i];
    FORU(i, 1, n) cin >> b[i];
    FORU(i, 1, n) f[i] = 1;
    FOR(i, 0, 1 << M) cnt[i] = __builtin_popcount(i);

    int pos = 0;
    FORU(i, 1, n){
        int pref = (a[i] >> M);
        int suff = a[i] - (pref << M);

        FOR(mask, 0, 1 << M){
            int k = b[i] - cnt[pref & mask];
            if(k < 0 || k > M) continue;
            int j = dp[mask][suff][k];
            if(f[i] < f[j] + 1){
                f[i] = f[j] + 1;
                t[i] = j;
            }
        }

        if(f[i] > f[pos]) pos = i;

        FOR(mask, 0, 1 << M){
            int k = cnt[suff & mask];
            if(f[dp[pref][mask][k]] < f[i]){
                dp[pref][mask][k] = i;
            }
        }
    }

    cout << f[pos] << "\n";
    vector<int> ans;
    while(pos != 0) ans.eb(pos), pos = t[pos];
    FORD(i, ans.size() - 1, 0) cout << ans[i] << " ";
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'void Fi()':
subsequence.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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