(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

제출 #572801

#제출 시각아이디문제언어결과실행 시간메모리
572801vovamrLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
2178 ms84492 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("-O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,popcnt,tune=native") #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } #define cnt(x) __builtin_popcount((x)) const int N = 10; const int MX = 1e6 + 10; int ek[MX]; int dp[1 << N][1 << N][N << 1]; inline void solve() { int n; cin >> n; ve<int> a(n), b(n); for (auto &i : a) cin >> i; for (auto &i : b) cin >> i; for (int i = 0; i < n; ++i) { int x = a[i]; int les10 = x & ((1 << 10) - 1); int big10 = x >> 10; chmax(ek[i], 1); for (int p = 0; p < (1 << 10); ++p) { int hui = cnt(p & x); if (hui > b[i] || b[i] - hui > 10) continue; chmax(ek[i], dp[p][big10][b[i] - hui] + 1); } for (int p = 0; p < (1 << 10); ++p) { int hui = cnt(p & big10); chmax(dp[les10][p][hui], ek[i]); } } ve<int> ans; int mx = max_element(ek, ek + n) - ek; int pos = mx, i = mx - 1; ans.pb(pos); while (~i) { if (cnt(a[i] & a[pos]) == b[pos] && ek[pos] == ek[i] + 1) { ans.pb(i); pos = i; --i; } else --i; } reverse(all(ans)); cout << sz(ans) << '\n'; for (auto &i : ans) cout << i + 1 << " "; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...