Submission #1115125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115125		adiyer	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3266 ms	95012 KiB

subsequence

// #pragma optimize ("g",on)
// #pragma GCC optimize("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
 
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
 
using namespace std;
 
typedef long long ll;
 
const int N = 1e5 + 2;
const int M = (1 << 10);
 
ll n, pos;
ll a[N], k[N], par[N], ans[N], dp[M][M][11];
 
void sol(){
	cin >> n, pos = 1;
	for(ll i = 1; i <= n; i++) cin >> a[i], ans[i] = 1, par[i] = i;
	for(ll i = 1; i <= n; i++) cin >> k[i];
	for(ll i = 1; i <= n; i++){
		for(ll msk = 0; msk < M; msk++){
			ll add = k[i] - __builtin_popcount((msk & (a[i] >> 10)));
			if(add < 0 || add > 10) continue;
			ll j = dp[msk][a[i] % M][add];
			if(ans[j] + 1 > ans[i]) ans[i] = ans[j] + 1, par[i] = j;
		}
		for(ll msk = 0; msk < M; msk++){
			ll add = __builtin_popcount((msk & (a[i] % M)));
			ll &j = dp[(a[i] >> 10)][msk][add];
			if(ans[j] < ans[i]) j = i;
		}
		if(ans[pos] < ans[i]) pos = i;
	}
	vector < ll > vec = {pos};
	while(vec.size() < ans[vec[0]]) pos = par[pos], vec.pb(pos);
	reverse(vec.begin(), vec.end());
	cout << vec.size() << '\n';
	for(ll x : vec) cout << x << ' ';
}
 
signed main(){
	ios                     
	sol();
// 	slow();
//  stress();
}

Compilation message (stderr)

subsequence.cpp: In function 'void sol()':
subsequence.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   41 |  while(vec.size() < ans[vec[0]]) pos = par[pos], vec.pb(pos);
      |        ~~~~~~~~~~~^~~~~~~~~~~~~

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