Submission #386253

#	Time	Username	Problem	Language	Result	Execution time	Memory
386253		patrikpavic2	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2692 ms	98524 KiB

subsequence

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>

#define PB push_back

using namespace std;

const int N = 1e5 + 500;
const int MSK = (1 << 20);
const int BS = (1 << 10);

int n, A[N], K[N], dp[N], rek[N], krj;
int naj[MSK][11], sol, naj2[MSK][11];
vector < int > na[BS][11];

void dodaj(int xx, int y, int gdje){	
	int i = xx >> 10, x = xx & (BS - 1);
	for(int j = 0;j < BS;j++){
		int ds = __builtin_popcount(j & x);
		if(y > naj[(i << 10) + j][ds]){
			naj[(i << 10) + j][ds] = y;
			naj2[(i << 10) + j][ds] = gdje;
		}
	}
}

int GDJE;

int pitaj(int x, int k){
	int ret = 0, i = x >> 10;
	for(int kk = 0;kk < 11;kk++){
		if(k - kk < 0 || k - kk > 10) continue;
		for(int j : na[i][kk]){
			if(naj[(j << 10) + (x & (BS - 1))][k - kk] > ret){
				ret = naj[(j << 10) + (x & (BS - 1))][k - kk];
				GDJE = naj2[(j << 10) + (x & (BS - 1))][k - kk];
			}
		}
	}
	return ret;
}

int main(){
	for(int i = 0;i < BS;i++)
		for(int j = 0;j < BS;j++)
			na[i][__builtin_popcount(i & j)].PB(j);
	scanf("%d", &n);
	for(int i = 0;i < n;i++)
		scanf("%d", A + i);
	for(int i = 0;i < n;i++)
		scanf("%d", K + i);
	for(int i = 0;i < n;i++){
		dp[i] = pitaj(A[i], K[i]) + 1;
		if(dp[i] > 1){
			rek[i] = GDJE;
		}
		if(sol < dp[i]){
			sol = dp[i];
			krj = i;
		}
		dodaj(A[i], dp[i], i);
	}
	printf("%d\n", sol);
	vector < int > fin;
	for(;;){
		fin.PB(krj + 1);
		if(dp[krj] == 1) break;
		krj = rek[krj];
	}
	reverse(fin.begin(), fin.end());
	for(int x : fin)
		printf("%d ", x);
	printf("\n");
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
subsequence.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%d", K + i);
      |   ~~~~~^~~~~~~~~~~~~

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