Submission #1159154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159154		PieArmy	Longest beautiful sequence (IZhO17_subsequence)	C++20	40 / 100	164 ms	2000 KiB

subsequence

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n;
int a[100023],k[100023];
int ans[100023],par[100023],bes[(1<<8)];

void code(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>k[i];
	}
	int mx=1;
	for(int i=1;i<=n;i++){
		ans[i]=1;
		par[i]=0;
		if(n<=5000){
			for(int j=1;j<i;j++){
				int x=(a[j]&a[i]);
				int cnt=0;
				for(int l=0;l<20;l++){
					if(x&pie(l))cnt++;
				}
				if(cnt==k[i]&&ans[i]<ans[j]+1){
					ans[i]=ans[j]+1;
					par[i]=j;
				}
			}
		}
		else for(int j=0;j<pie(8);j++){
			int x=(j&a[i]);
			int cnt=0;
			for(int l=0;l<8;l++){
				if(x&pie(l))cnt++;
			}
			if(cnt==k[i]&&ans[i]<ans[bes[j]]+1){
				ans[i]=ans[bes[j]]+1;
				par[i]=bes[j];
			}
		}
		if(ans[i]>ans[mx])mx=i;
		if(n>5000)if(ans[i]>ans[bes[a[i]]])bes[a[i]]=i;
	}
	cout<<ans[mx]<<endl;
	vector<int>v;
	while(mx){
		v.pb(mx);
		mx=par[mx];
	}
	while(v.size()){
		cout<<v.back()<<" ";
		v.pop_back();
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	int t=1;
	if(!t)cin>>t;
	while(t--){code();cout<<endl;}
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:71:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~
subsequence.cpp:71:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~

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