Submission #948857

#	Time	Username	Problem	Language	Result	Execution time	Memory
948857		VinhLuu	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	4 ms	16732 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][1 << 10 - 1], id[22][1 << 10 - 1][1 << 10 - 1], 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);
        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){
                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(mx > f[u][msk][m2]){
                f[u][msk][m2] = mx;
                id[u][msk][m2] = i;
            }
        }
        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:18:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   18 | int n, f[22][1 << 10 - 1][1 << 10 - 1], id[22][1 << 10 - 1][1 << 10 - 1], a[N], k[N], ans, trace[N];
      |                   ~~~^~~
subsequence.cpp:18:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   18 | int n, f[22][1 << 10 - 1][1 << 10 - 1], id[22][1 << 10 - 1][1 << 10 - 1], a[N], k[N], ans, trace[N];
      |                                ~~~^~~
subsequence.cpp:18:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   18 | int n, f[22][1 << 10 - 1][1 << 10 - 1], id[22][1 << 10 - 1][1 << 10 - 1], a[N], k[N], ans, trace[N];
      |                                                     ~~~^~~
subsequence.cpp:18:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   18 | int n, f[22][1 << 10 - 1][1 << 10 - 1], id[22][1 << 10 - 1][1 << 10 - 1], a[N], k[N], ans, trace[N];
      |                                                                  ~~~^~~
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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:50:33: warning: iteration 512 invokes undefined behavior [-Waggressive-loop-optimizations]
   50 |             if(mx > f[u][msk][m2]){
      |                     ~~~~~~~~~~~~^
subsequence.cpp:48:30: note: within this loop
   48 |         for(int msk = 0; msk < (1 << s); msk ++){
      |                          ~~~~^~~~~~~~~~

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