Submission #172914

#	Time	Username	Problem	Language	Result	Execution time	Memory
172914		VEGAnn	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	5 ms	888 KiB

subsequence

#include <bits/stdc++.h>
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize ("-O3")
//#pragma GCC optimize ("Ofast")
#define sz(x) ((int)x.size())
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 100100;
//const int N2 = N * N;
const int PW = 8;
const int VL = (1 << PW) + 1;
const int oo = 2e9;
vector<int> sp[VL][PW + 1], vc;
int nt[N][VL], f[N][VL], n, a[N], k[N];
short pr[N][VL], loc;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("in.txt","r",stdin);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> k[i];
    for (int i = 0; i < VL; i++)
        nt[n][i] = n;
    for (int i = n - 1; i >= 0; i--){
        for (int j = 0; j < VL; j++)
            nt[i][j] = nt[i + 1][j];
        if (i < n - 1)
            nt[i][a[i + 1]] = i + 1;
    }

//    cerr <<  __builtin_popcount(3 & 5) << '\n';

    for (int i = 0; i < VL; i++){
//        cerr << i << '\n';
        for (int j = 0; j < VL; j++) {
//            cerr << j << '\n';
            sp[i][__builtin_popcount(i & j)].PB(j);
        }
    }


    for (int i = 1; i <= n + 1; i++)
        fill(f[i], f[i] + VL, n);
    for (int i = 0; i < n; i++)
        if (f[1][a[i]] == n)
            f[1][a[i]] = i;

    int ans = 1;
    for (; ;ans++){
        bool was = 0;
        int ck = k[ans];
        for (int i = 0; i < VL; i++){
            if (f[ans][i] == n) continue;
            was = 1;
            loc = i;
            int ps = f[ans][i];

            if (ck > 8) continue;

            for (int cans : sp[i][ck]) {
                int nw = nt[ps][cans];
                if (f[ans + 1][cans] > nw){
                    f[ans + 1][cans] = nw;
                    pr[ans + 1][cans] = i;
                }
            }
        }

        if (!was){
            ans--;
            break;
        }
    }

    cout << ans << '\n';
    vc.clear();

    while (1){
        vc.PB(f[ans][loc]);
        if (ans == 1) break;
        loc = pr[ans][loc];
        ans--;
    }

    reverse(all(vc));
    for (int x : vc)
        cout << x + 1 << " ";
    return 0;
}

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