제출 #344095

#제출 시각아이디문제언어결과실행 시간메모리
344095IZhO_2021_I_want_SilverLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
390 ms262148 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx") #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> #include <iomanip> #include <cassert> #include <stack> #include <queue> #include <deque> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp>- using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; // template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // order_of_key (k) : Number of items strictly smaller than k . // find_by_order(k) : K-th element in a set (counting from zero). #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define ppb pop_back #define mkp make_pair #define F first #define S second #define lb lower_bound #define ub upper_bound #define show(a) cerr << #a <<" -> "<< a <<" " #define nl cerr <<"\n" //#define int ll const int N = 1e5 + 5; const int oo = 1e9 + 5; int n, a[N], k[N], pre[N], bit[N]; pii dp[N]; vector <int> vec; void solve() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= n; ++i) { cin >> k[i]; } for (int i = 0; i <= (1 << 10); ++i) { bit[i] = __builtin_popcount(i); } for (int i = 1; i <= n; ++i) { dp[a[i]] = max(dp[a[i]], {1, i}); if (bit[a[i]] < k[i]) { continue; } for (int m = 0; m < (1 << 10); ++m) { if (bit[m] < k[i]) { continue; } if (__builtin_popcount(a[i] & m) != k[i]) { continue; } if (dp[a[i]].F < dp[m].F + 1) { dp[a[i]] = {dp[m].F + 1, i}; pre[i] = dp[m].S; } } } int ans = 0, pos = 0; for (int i = 0; i <= (1 << 10); ++i) { if (ans < dp[i].F) { ans = dp[i].F; pos = dp[i].S; } } while (pre[pos]) { vec.pb(pos); pos = pre[pos]; } vec.pb(pos); reverse(all(vec)); cout << sz(vec) <<"\n"; for (int i = 0; i < sz(vec); ++i) { cout << vec[i] <<" "; } } main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int tests = 1; //cin >> tests; while (tests --) { solve(); } return 0; } /* Just Chalish! 4 1 2 3 4 10 0 1 0 2 8 9 20 0 5 5 3 5 3 5 10 1 20 1 20 */

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

subsequence.cpp:90:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 |  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...