Submission #781325

#	Time	Username	Problem	Language	Result	Execution time	Memory
781325		vgoofficial	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	143 ms	185128 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int bitCount[1<<10][1<<10];
vector<vector<vector<int>>> maxAns(1<<10, vector<vector<int>>(1<<10, vector<int>(11, -1)));
vector<vector<vector<int>>> rightSide(1<<10, vector<vector<int>>(1<<10, vector<int>(11, -1)));
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    int n;
    cin >> n;
    int a[n], k[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 < 1<<10; i++) {
        for(int j = 0; j < 1<<10; j++) {
            bitCount[i][j]=__builtin_popcount(i&j);
        }
    }

    vector<int> ans(n, 1);
    vector<int> prev(n, -1);
    for(int i = 0; i < n; i++) {
        //cout << i << endl;
        int left = a[i]>>10;
        int right = a[i]%(1<<10);
        for(int j = 0; j < (1<<10); j++) {
            //cout << i << " " << j << endl;
            int leftAnd = bitCount[left][j];
            int rightAnd = k[i]-leftAnd;
            if(rightAnd<0||rightAnd>10) continue;
            //cout << i << " " << j << " " << left << " " << right << " " << leftAnd << " " << rightAnd << endl;
            //cout << maxAns[left][right][rightAnd]+1 << ans[i] << endl;
            if(maxAns[j][right][rightAnd]+1>ans[i]) {
                ans[i]=maxAns[left][right][rightAnd]+1;
                prev[i]=rightSide[left][right][rightAnd];
                //cout << i << " " << maxAns[left][right][rightAnd]+1 << " " << j << " " << rightSide[left][right][rightAnd] << " " << prev[i] << endl;
            }
        }
        for(int j = 0; j < 1<<10; j++) {
            //cout << "second " << i << " " << j << endl;
            if(maxAns[left][j][bitCount[j][right]]<ans[i]) {
                maxAns[left][j][bitCount[j][right]]=ans[i];
                rightSide[left][j][bitCount[j][right]]=i;
            }
        }
        //cout << "line 52 " << i << " " << n << endl;
    }
    //cout << "out of loop" << endl;
    int bestIndex = 0;
    int most = ans[0];
    for(int i = 1; i < n; i++) {
        if(ans[i]>most) {
            most=ans[i];
            bestIndex=i;
        }
    }
    string answ = to_string(1+bestIndex);
    while(prev[bestIndex]!=-1) {
        bestIndex=prev[bestIndex];
        answ=to_string(1+bestIndex)+" "+answ;
    }
    cout << most << endl << answ << endl;
}
/*
4
1 2 3 4
10 0 1 0
*/

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