Submission #344116

#TimeUsernameProblemLanguageResultExecution timeMemory
344116IZhO_2021_I_want_SilverLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
1 ms492 KiB
#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef pair <int, int> pii; #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define F first #define S second const int N = 1e5 + 5; const int MX = (1 << 10) + 5; int n, a[N], k[N], pre[N]; pii dp[MX]; 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 = 1; i <= n; ++i) { for (int m = 0; m < MX-5; ++m) { if (__builtin_popcount((a[i] & m)) != k[i]) { continue; } //if (a[i] == m) { continue; } if (dp[a[i]].F < dp[m].F + 1) { pre[i] = dp[m].S; dp[a[i]] = {dp[m].F + 1, i}; } } dp[a[i]] = max(dp[a[i]], {1, i}); } int ans = 0, pos = 0; for (int i = 0; i < MX-5; ++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] <<" "; } } int 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...