Submission #697004

#	Time	Username	Problem	Language	Result	Execution time	Memory
697004		allllekssssa	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6040 ms	3800 KiB

subsequence

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define pb push_back

const int maxN = 1e6 + 10;

int a[maxN], k[maxN];
int n;
map<int, pii> dp;
int rz[maxN], pre[maxN];

int main() {
    
    cin >> n;

    for (int i = 1; i<=n; i++) {
    	scanf("%d", &a[i]);
    }

    for (int i = 1; i<=n; i++) {
    	scanf("%d", &k[i]);
    }
    
    int ans = 0;
    
    for (int i = 1; i<=n; i++) {
        int best = 0;
        int idx = 0;

        for (auto j: dp) {
        	if (__builtin_popcount(a[i] & j.first) == k[i]) {
        		if (j.second.first > best) {
        			best = j.second.first;
        			idx = j.second.second;
        		}	
        	}
        }
        
        if (dp[a[i]].first < best + 1) {
        	dp[a[i]] = {best + 1, i};
        	rz[i] = best + 1;
        	pre[i] = idx;
        }

        if (rz[i] > rz[ans]) ans = i;
    }

    cout << rz[ans] << endl;
    
    vector<int> indices; 

    while(rz[ans] != 0) {
    	indices.pb(ans);
    	ans = pre[ans];
    }

    reverse(indices.begin(), indices.end());

    for (auto i: indices) {
    	printf("%d ", i);
    }

    printf("\n");

	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:20:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |      scanf("%d", &a[i]);
      |      ~~~~~^~~~~~~~~~~~~
subsequence.cpp:24:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |      scanf("%d", &k[i]);
      |      ~~~~~^~~~~~~~~~~~~

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