Submission #42611

#	Time	Username	Problem	Language	Result	Execution time	Memory
42611		almasalmas	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4099 ms	114368 KiB

subsequence

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;

int a[100001];
int b[100001];
int d[11][1025][1025];
int pr[11][1025][1025];
int dr[100001];
vector <int> ans;

int main () {
//	freopen ("subsequence.in", "r", stdin);
//	freopen ("subsequence.out", "w", stdout);
	int n;   
	scanf ("%d", &n);
	int mx = -1, pos;
	for (int i = 1;i <= n;i ++) 
		scanf ("%d", a + i);;
	for (int i = 1;i <= n;i ++) 
		scanf ("%d", b + i);
	for (int i = 1;i <= n;i ++) {
	    int asd = 0;
	    int mask1 = a[i] >> 10;             
		for (int j = 0;j < (1 << 10);j ++) {
			int kol = b[i] - (__builtin_popcount (j & a[i]));
			if (kol < 0 || kol > 10) continue;
			if (d[kol][j][mask1] > asd) {
				asd = d[kol][j][mask1];
				dr[i] = pr[kol][j][mask1];
			}
		}
		asd ++;   
		for (int j = 0;j < (1 << 10);j ++) {
		    int mask = (a[i] & ((1 << 10) - 1));
			int kol = __builtin_popcount (mask1 & j);
			if (asd > d[kol][mask][j]) {
				d[kol][mask][j] = asd;
				pr[kol][mask][j] = i;
			} 		
		}
		if (asd > mx) {
			mx = asd;
			pos = i;
		}
	}                   
	printf ("%d\n", mx);
	while (pos) {
		ans.push_back (pos);
		pos = dr[pos];
	}
	reverse (ans.begin (), ans.end ());
	for (auto to : ans)   
		printf ("%d ", to);
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:18:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
                  ^
subsequence.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", a + i);;
                      ^
subsequence.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", b + i);
                      ^

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