Submission #697032

#	Time	Username	Problem	Language	Result	Execution time	Memory
697032		allllekssssa	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6022 ms	4100 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[21];
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;
        int currentBitCnt = __builtin_popcount(a[i]);

       for (int bCnt = k[i]; bCnt <= 20; bCnt++) {
            int minPresek = bCnt + currentBitCnt - 20;
            if (minPresek > k[i]) continue;
            if (currentBitCnt < k[i]) continue;
            for (auto j: dp[bCnt]) {
        	   if (__builtin_popcount(a[i] & j.first) == k[i]) {
        		  if (j.second.first > best) {
        			best = j.second.first;
        			idx = j.second.second;
        		   }	
         	   }
            }
       }
        
        if (dp[currentBitCnt][a[i]].first < best + 1) {
        	dp[currentBitCnt][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