Submission #36342

#	Time	Username	Problem	Language	Result	Execution time	Memory
36342		ToMoClone	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	0 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 cnt = bitcount[i] - __builtin_popcount(mask & pref);
    			if(cnt < 0) 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 = __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:17: 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:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &n);
                     ^
subsequence.cpp:20:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &a[i]);
                         ^
subsequence.cpp:22:32: 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