제출 #778976

#제출 시각아이디문제언어결과실행 시간메모리
778976magicianLongest beautiful sequence (IZhO17_subsequence)C++14
23 / 100
391 ms262144 KiB
#include<iostream> #include<vector> #include<algorithm> #define MASK(x) (1LL << (x)) #define BIT(x, i) (((x) >> (i)) & 1) using namespace std; const int N = (int)1e5 + 1; int n; int a[N], k[N]; bool maximize(int& a, const int& b) { if(a < b) { a = b; return true; } return false; } void print_ans(vector<int>& ans) { cout << ans.size() << '\n'; for(int i = 0; i < (int)ans.size(); i++) cout << ans[i] << ' '; cout << '\n'; } void brute_force(void) { vector<int> f(n + 1, 0), trace(n + 1, -1); int p = 1; for(int i = 1; i <= n; i++) { f[i] = 1; trace[i] = -1; for(int j = 1; j < i; j++) { if(__builtin_popcount(a[i] & a[j]) == k[i]) { if(maximize(f[i], f[j] + 1)) { trace[i] = j; } } } if(f[i] > f[p]) p = i; } vector<int> ans; for(int i = p; i != -1; i = trace[i]) { ans.push_back(i); } reverse(ans.begin(), ans.end()); print_ans(ans); } void slow_bitmask_dp(int max_log = 20) { vector<pair<int, int> > f(MASK(max_log), make_pair(0, -1)); vector<int> trace(n + 1, -1); int p = -1; for(int i = 1; i <= n; i++) { if(maximize(f[a[i]].first, 1)) { f[a[i]].second = i; trace[i] = -1; } for(int mask = 0; mask < MASK(max_log); mask++) { if(__builtin_popcount(mask & a[i]) == k[i]) { if(maximize(f[a[i]].first, f[mask].first + 1)) { trace[i] = f[mask].second; f[a[i]].second = i; } } } if(p == -1 || f[a[i]] > f[p]) p = a[i]; } vector<int> ans; for(int i = f[p].second; i != -1; i = trace[i]) { ans.push_back(i); } reverse(ans.begin(), ans.end()); print_ans(ans); } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i <= n; i++) { cin >> k[i]; } //slow_bitmask_dp(8); if(n <= 5000) { brute_force(); } else if(*max_element(a + 1, a + n + 1) < MASK(8)) { slow_bitmask_dp(8); } else { return 1; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...