Submission #36344

#	Time	Username	Problem	Language	Result	Execution time	Memory
36344		ToMoClone	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	0 ms	93300 KiB

subsequence

/*input
4
1 2 3 4
10 0 1 0
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
 
const int N = 100005, M = 1 << 10;
int n, a[N], bitcount[N], trace[N];
pair<int, int> f[M][M][11], ans;
 
int pop_count(int v){
	v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
	return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
}
 
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &bitcount[i]);
 
	for(int i = 1; i <= n; ++i){
		int pref = a[i] >> 10, suf = a[i] - (pref << 10);
		pair<int, int> cur = {0, 0};
		for(int mask = 0; mask < M; ++mask){
			int cnt = bitcount[i] - pop_count(mask & pref);
			if(cnt < 0 || cnt > 10) continue;
			cur = max(cur, {f[mask][suf][cnt].first + 1, f[mask][suf][cnt].second});
		}
		trace[i] = cur.second;
 
		cur.second = i;
		for(int mask = 0; mask < M; ++mask){
			int cnt = pop_count(mask & suf);
			f[pref][mask][cnt] = max(f[pref][mask][cnt], cur);
		}
 
		if(ans.first < cur.first) ans = make_pair(cur.first, i);
	}
 
	vector<int> res;
	while(ans.second){
		res.push_back(ans.second);
		ans.second = trace[ans.second];
	}
	reverse(res.begin(), res.end());
 
	printf("%d\n", (int)res.size());
	for(int i = 0; i < (int)res.size(); ++i)
		printf("%s%d", i ? " " : "", res[i]);
}

Compilation message (stderr)

subsequence.cpp: In function 'int pop_count(int)':
subsequence.cpp:17:13: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
             ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:21:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
subsequence.cpp:23:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^
subsequence.cpp:25:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &bitcount[i]);
                            ^

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