Submission #686052

#	Time	Username	Problem	Language	Result	Execution time	Memory
686052		dostigator	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	342 ms	2764 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<=1000; ++i){
    		pos[i]=-1;
    	}
    	for(int i=1; i<=n; ++i){
    		cin>>a[i];
			pr[i]=-1;
    		bg=max(bg,a[i]);
    		dp[i]=1;
    	}for(int i=1; i<=n; ++i)cin>>k[i];
		if(bg<1000){
    		int ans=1,r=1;
    	for(int i=1; i<=n; ++i){
    		for(int x=0; x<1000; ++x){
    			int num=(a[i]&x);
				num=__builtin_popcount(num);
				if(num==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;
    			}
    		}if(pos[a[i]]==-1 || dp[i]>dp[pos[a[i]]]) pos[a[i]]=i;
    	}//cout<<ans<<endl;
    	vt<int>lst;
    	while(r!=-1){
    		lst.pb(r);
    		r=pr[r];
		}if(ans!=lst.size())1/0;
		cout<<lst.size()<<endl;
    	reverse(all(lst));
    	for(int x:lst){
    		cout<<x<<' ';
    	}cout<<endl;
    		return;
    	}
    	if(n<=5000){
			int f=1,ps=1;
			for(int i=1; i<=n; ++i){
				for(int j=1; j<i; ++j){
					if(__builtin_popcount((a[i]&a[j]))==k[i]){
						dp[i]=max(dp[i],dp[j]+1);
						if(dp[i]==dp[j]+1)pr[i]=j;
						f=max(f,dp[i]);
						if(f==dp[i])ps=i;
					}
				}
			}cout<<f<<endl;
			vt<int>lst;
			while(ps!=-1){
				lst.pb(ps);
				ps=pr[ps];
			}reverse(all(lst));
			for(int x:lst)cout<<x<<' ';
			cout<<endl;
			return;
		}	
    }
    
    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:63:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   }if(ans!=lst.size())1/0;
      |       ~~~^~~~~~~~~~~~
subsequence.cpp:63:24: warning: division by zero [-Wdiv-by-zero]
   63 |   }if(ans!=lst.size())1/0;
      |                       ~^~
subsequence.cpp:63:24: warning: statement has no effect [-Wunused-value]
subsequence.cpp: In function 'int main()':
subsequence.cpp:99:15: warning: unused variable 'lolol' [-Wunused-variable]
   99 |      int tt=1,lolol=0;
      |               ^~~~~

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