제출 #540964

#제출 시각아이디문제언어결과실행 시간메모리
540964vinnipuh01Longest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
287 ms262144 KiB
#include <iostream> #include <bits/stdc++.h> #include <cmath> #include <algorithm> #include <vector> #include <deque> #include <set> #include <stack> #include <string> #include <map> #include <queue> #define int long long using namespace std; const long long oo = 1000000000000000000; long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen ( "sum.in", "r", stdin ) */ int n, a[ 100001 ], b[ 100001 ], mp[ 100001 ], p[ 100001 ], mpp[ 2000001 ], bl[ 100001 ]; vector <int> v; main () { cin >> n; for ( int i = 0; i <= 2000000; i ++ ) { mpp[ i ] = __builtin_popcount( i ); } for ( int i = 1; i <= n; i ++ ) cin >> a[ i ]; for ( int i = 1; i <= n; i ++ ) cin >> b[ i ]; if ( n <= 5000 ) { mp[ 1 ] = 1; p[ 1 ] = -1; for ( int i = 2; i <= n; i ++ ) { p[ i ] = -1; mp[ i ] = 1; for ( int j = i - 1; j >= 1; j -- ) { if ( mpp[ ( a[ i ] & a[ j ] ) ] == b[ i ] && mp[ i ] < mp[ j ] + 1 ) { mp[ i ] = mp[ j ] + 1; p[ i ] = j; } } } mx = 0; for ( int i = 1; i <= n; i ++ ) { if ( mx < mp[ i ] ) { mx = mp[ i ]; pos = i; } } for ( int i = pos; i != -1; i = p[ i ] ) { v.push_back( i ); } cout << mx << "\n"; reverse( v.begin(), v.end() ); for ( auto i : v ) cout << i << " "; return 0; } for ( int i = 1; i <= n; i ++ ) mx = max( mx, a[ i ] ); bl[ a[ 1 ] ] = 1; p[ 1 ] = -1; mp[ a[ 1 ] ] = 1; for ( int i = 2; i <= n; i ++ ) { for ( int j = 0; j <= mx; j ++ ) { if ( mpp[ ( a[ i ] & j ) ] == b[ i ] && mp[ j ] + 1 > mp[ a[ i ] ] ) { mp[ a[ i ] ] = mp[ j ] + 1; p[ i ] = bl[ j ]; bl[ a[ i ] ] = i; } } } for ( int i = 1; i <= n; i ++ ) { if ( mx < mp[ a[ i ] ] ) { mx = mp[ a[ i ] ]; pos = i; } } for ( int i = pos; i != -1; i = p[ i ] ) v.push_back( i ); cout << v.size() << "\n"; reverse( v.begin(), v.end() ); for ( auto i : v ) cout << i << " "; }

컴파일 시 표준 에러 (stderr) 메시지

subsequence.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main () {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...