Submission #948876

#	Time	Username	Problem	Language	Result	Execution time	Memory
948876		VinhLuu	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3789 ms	73924 KiB

subsequence

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e5 + 5;
//const ll oo = 1e18;
const int mod = 998244353;
//const int base = 23;

int n, f[22][1 << 10][1 << 10], id[22][1 << 10][1 << 10], a[N], k[N], ans, trace[N];

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

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n;
    int s = 10, tmp = 1;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i =1 ; i <= n; i ++) cin >> k[i];
    for(int i = 1; i <= n; i ++){
        int x = a[i];
        int m1 = (x >> s);
//        cout << (m1 << s) << " " << x << "e\n";
        int m2 = ((m1 << s) ^ x);
//        cout << i << " " << m1 << " " << m2 << "f\n";
        int mx = 1;
        for(int msk = 0; msk < (1 << s); msk ++){
            int u = __builtin_popcount(msk & m2);
            if(u > k[i]) continue;
            int val = f[k[i] - u][m1][msk] + 1;
            if(val > mx){
//                cout << k[i] - u << " " << m1 << " " << msk << " " << val << " " << f[k[i] - u][m1][msk] << "l\n";
                mx = val;
                trace[i] = id[k[i] - u][m1][msk];
            }
        }
        for(int msk = 0; msk < (1 << s); msk ++){
            int u = __builtin_popcount(msk & m1);
            if(u > 20) continue;
            if(mx > f[u][msk][m2]){
                f[u][msk][m2] = mx;
                id[u][msk][m2] = i;
//                if(msk == 0) cout << u << " " << msk << " " << m2 << " " << mx << "r\n";
            }
        }
        if(mx > ans) ans = mx, tmp = i;
    }
    cout << ans << "\n";
    vector<int> vr;
    vr.pb(tmp);
    while(trace[tmp]){
        tmp = trace[tmp];
        vr.pb(tmp);
    }
    reverse(all(vr));
    for(auto j : vr) cout << j << " ";

}

Compilation message (stderr)

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

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