Submission #36348

#	Time	Username	Problem	Language	Result	Execution time	Memory
36348		ToMoClone	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5686 ms	93444 KiB

subsequence

/*input
5
5 3 5 3 5
10 1 20 1 20
*/
#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], Bit[M];
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 = 0; i < M; ++i)
		Bit[i] = pop_count(i);
 
	for(int i = 1; i <= n; ++i){
		int pref = a[i] >> 10, suf = a[i] % M, cur = 1, save = 0;
		for(int mask = 0; mask < M; ++mask){
			int cnt = bitcount[i] - Bit[mask & pref];
			if(cnt < 0 || 10 < cnt) continue;

			if(cur < f[mask][suf][cnt].first + 1)
				cur = f[mask][suf][cnt].first + 1, save = f[mask][suf][cnt].second;
		}
		trace[i] = save;
 
		for(int mask = 0; mask < M; ++mask){
			int cnt = Bit[mask & suf];
			if(f[pref][mask][cnt].first < cur)
				f[pref][mask][cnt] = make_pair(cur, i);
		}
		if(ans.first < cur) ans = make_pair(cur, 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: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60