Submission #673561

#	Time	Username	Problem	Language	Result	Execution time	Memory
673561		Cutebol	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5191 ms	173528 KiB

subsequence

#include <bits/stdc++.h>
 
using namespace std;
 
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define Scaramouche ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
   
const int N = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e9 ;

int n , m ;
int a[N] , b[N] , dp[N] , p[N] ;
int vec[2000][2000][20] ;

int bt( int i ){
	return __builtin_popcount(i) ;
}

void solve(){
	
	cin >> n ;
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
	for ( int i = 1 ; i <= n ; i ++ ) cin >> b[i] ;
	for ( int i = 1 ; i <= n ; i ++ ){
		int l = (a[i]>>10) ;
		int r = (a[i]&(1<<10)-1) ;
		int ans = 0 ;
		for ( int j = 0 ; j < ( 1 << 10 ) ; j ++ ){
			int x = b[i]-bt(j&r) ;
			if ( x<0 || x>10 ) continue ;
			if ( dp[ans]<dp[vec[l][j][x]] ) ans = vec[l][j][x] ;
		}
		dp[i] = dp[ans]+1 ;
		p[i] = ans ;
		for ( int j = 0 ; j < 1 << 10 ; j ++ ){
			itn x = bt(j&l) ;
			if ( dp[i]> dp[vec[j][r][x]] ) vec[j][r][x] = i ;
		}
	}
	int ans = 1 ;
	for ( int i = 1 ; i <= n ; i ++ )
		if ( dp[i] > dp[ans] ) ans = i ;
	
	vector <int> res ;
	while ( ans != 0 ){
		res.push_back(ans) ;
		ans = p[ans] ;
	}
	reverse(res.begin() , res.end() ) ;
	cout << res.size() <<endl ;
	for ( auto i : res ) cout << i << ' ' ;
}
 
signed main(){
//  fopn("blocks") ;
    Scaramouche ;
    int t = 1 ;
//    	cin >> t ;
    while ( t -- ) solve() ; 
}

Compilation message (stderr)

subsequence.cpp: In function 'void solve()':
subsequence.cpp:32:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   32 |   int r = (a[i]&(1<<10)-1) ;
      |                 ~~~~~~~^~
subsequence.cpp: In function 'void fopn(std::string)':
subsequence.cpp:5:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:5:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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