Submission #685431

#	Time	Username	Problem	Language	Result	Execution time	Memory
685431		dostigator	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	0 ms	340 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
#define Y second
#define X first
typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
const ll INF=1e18;
const int inf=1e9;
const int N=2e6+505;
const int M=3e3+10;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

/*From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH*/

int n,a[N],k[N];
int dp[N],pr[N],pos[N];

void solve(){
	cin>>n;
	int bg=0;
	for(int i=0; i<=256; ++i){
		pos[i]=-1;
		pr[i]=-1;
	}
	for(int i=1; i<=n; ++i){
		cin>>a[i];
		bg=max(bg,a[i]);
		dp[i]=1;
	}for(int i=1; i<=n; ++i)cin>>k[i];
	if(bg<=256){
		int ans=1,r=1;
	for(int i=1; i<=n; ++i){
		for(int x=0; x<=256; ++x){
			if(__builtin_popcount(a[i]&x)==k[i] && pos[x]!=-1){
				int ps=pos[x];
				dp[i]=max(dp[i],dp[ps]+1);
				if(dp[i]==dp[ps]+1)pr[i]=ps;
				ans=max(ans,dp[i]);
				if(ans==dp[i])r=i;
			}
		}pos[a[i]]=i;
	}cout<<ans<<endl;
	vt<int>lst;
	while(r!=-1){
		lst.pb(r);
		r=pr[r];
	}if(ans!=lst.size())cout<<1/0;
	reverse(all(lst));
	for(int x:lst){
		cout<<x<<' ';
	}cout<<endl;
		return;
	}1/0;
}

int main(){
	//srand(time(0));
	//freopen("hotel.in","r",stdin);
	//freopen("hotel.out","w",stdout);
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tt=1,lolol=0;
//	cin>>tt;
	while(tt--) {
		//cout<<"Case "<<++lolol<<": ";
		solve();
	}
}

Compilation message (stderr)

subsequence.cpp: In function 'void solve()':
subsequence.cpp:61:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  }if(ans!=lst.size())cout<<1/0;
      |      ~~~^~~~~~~~~~~~
subsequence.cpp:61:29: warning: division by zero [-Wdiv-by-zero]
   61 |  }if(ans!=lst.size())cout<<1/0;
      |                            ~^~
subsequence.cpp:67:4: warning: division by zero [-Wdiv-by-zero]
   67 |  }1/0;
      |   ~^~
subsequence.cpp:67:4: warning: statement has no effect [-Wunused-value]
subsequence.cpp: In function 'int main()':
subsequence.cpp:75:11: warning: unused variable 'lolol' [-Wunused-variable]
   75 |  int tt=1,lolol=0;
      |           ^~~~~

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