Submission #36338

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

subsequence

/*input
*/
#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][10], 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 cntleft = bitcount[i] - __builtin_popcount(mask & pref);
			cur = max(cur, {f[mask][suf][cntleft].first + 1, f[mask][suf][cntleft].second});
		}
		trace[i] = cur.second;

		cur.second = i;
		for(int mask = 0; mask < M; ++mask){
			int cnt = __builtin_popcount(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:14: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:18:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
subsequence.cpp:20:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^
subsequence.cpp:22: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