제출 #234778

#제출 시각아이디문제언어결과실행 시간메모리
234778muhammad_hokimiyonLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
5 ms512 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast") #define fi first #define se second #define ll long long #define dl double long using namespace std; const int NN = 2e6 + 7; const int N = 1e5 + 7; const int M = 22; const int mod = 998244353; const ll inf = 1e18 + 7; const dl rf = 1e-14; const int B = sqrt(N); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; int a[N]; int k[N]; pair < int , int > d[(1 << 8)]; int p[(1 << 8)]; void solve1() { cin >> n; for( int i = 1; i <= n; i++ ){ cin >> a[i]; } for( int i = 1; i <= n; i++ ){ cin >> k[i]; } pair < int , int > ans = {0 , 0}; for( int i = 1; i <= n; i++ ){ int mx = -1; for( int j = 0; j < (1 << 8); j++ ){ if( __builtin_popcount( (a[i] & j) ) == k[i] ){ if( mx == -1 || d[j].fi + 1 > d[mx].fi ){ mx = j; } } } if( mx != -1 ){ if( d[a[i]].fi < d[mx].fi + 1 ){ p[i] = d[mx].se; d[a[i]] = { d[mx].fi + 1 , i }; } }else d[a[i]] = {1 , i}; if( d[a[i]].fi > ans.fi ){ ans = d[a[i]]; } } cout << ans.fi << "\n"; vector < int > v; while( ans.se != 0 ){ v.push_back(ans.se); ans.se = p[ans.se]; } reverse( v.begin() , v.end() ); for( auto x : v )cout << x << " "; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen( "input.txt" , "r" , stdin ); //freopen( "output.txt" , "w" , stdout ); int cghf = 1;//cin >> cghf; while( cghf-- ){ solve1(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...