제출 #342979

#제출 시각아이디문제언어결과실행 시간메모리
342979vonatlusLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
1 ms1132 KiB
/// wa #pragma GCC optimize("O3") //#pragma comment(linker, "/STACK:36777216") #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define sz(x) (int) x.size() #define all(z) (z).begin(), (z).end() using namespace std; using ll = long long; using pii = pair<int, int>; const int MOD = 1e9 + 7; const int INF = 1e9 + 1e2; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void fin() { #ifdef AM freopen(".in", "r", stdin); #endif } const bool flag = 0; const int N = 1e5+10; int dp[N], p[N], pos[N]; void ma1n() { int n; cin >> n; vector<int> a(n); for (int& x : a) { cin >> x; } vector<int> k(n); for (int& x : k) { cin >> x; } memset(p, -1, sizeof(p)); memset(pos, -1, sizeof(pos)); for (int i = 0; i < n; ++i) { dp[a[i]] = max(1, dp[a[i]]); for (int mask = 0; mask < (1<<8); ++mask) { int cnt = __builtin_popcount(a[i]&mask); if (cnt == k[i] && dp[mask]+1 > dp[a[i]]) { dp[a[i]] = dp[mask]+1; p[i] = pos[mask]; } } pos[a[i]] = i; } int cur = pos[max_element(dp, dp+N)-dp]; vector<int> ans; while (~cur) { ans.pb(cur); cur = p[cur]; } reverse(all(ans)); cout << sz(ans) << "\n"; for (int x : ans) cout << x+1 << " "; } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr), fin(); int ts = 1; if (flag) { cin >> ts; } while (ts--) { ma1n(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...