Submission #398484

#	Time	Username	Problem	Language	Result	Execution time	Memory
398484		CSQ31	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3593 ms	175436 KiB

subsequence

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int dp[1024][1024][21]; //last 10 bits,first 10 bits
int par[1024][1024][21]; //which elem contributes the most to this current state
int last[100001];
int pc[1024];
int main()
{
	owo
	int n;
	cin>>n;
	for(int i=0;i<1024;i++)pc[i] = __builtin_popcount(i);
	vector<int>a(n),k(n);
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>k[i];
	int c = 1023;
	int mx = 0;
	vector<int>res(n);
	for(int i=0;i<n;i++){
		int x = a[i]>>10; //last 10
		int y = a[i]&c; //first 10
		int ans = 0;
		for(int j=0;j<1024;j++){
			//we fix the last 10 bits then last param is fixed
			//second param means is there a mask such that AND value of this shit is k
			if(k[i] >= pc[j&x]){
				if(ans < dp[j][y][k[i]-pc[j&x]] + 1){
					ans = dp[j][y][k[i]-pc[j&x]] + 1;
					last[i] = par[j][y][k[i]-pc[j&x]];
				}
				
			}
		}
		if(ans == 1)last[i] = -1;
		for(int j=0;j<1024;j++){
			if(ans > dp[x][j][pc[j&y]]){
				dp[x][j][pc[j&y]] = ans;
				par[x][j][pc[j&y]] = i;
			}
		}
		res[i] = ans;
		mx = max(ans,mx);
	}
	cout<<mx<<'\n';
	for(int i=0;i<n;i++){
		if(res[i] == mx){
			int cur = i;
			vector<int>p;
			while(cur != -1){
				p.pb(cur);
				cur = last[cur];
			}
			reverse(all(p));
			for(int x:p)cout<<x+1<<" ";
			return 0;
			
		}
	}
/*
4
1 2 3 4
10 0 1 0
5
5 3 5 3 5
10 1 20 1 20
2
8 9
20 0
* */
}

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