제출 #779030

#제출 시각아이디문제언어결과실행 시간메모리
779030magicianLongest beautiful sequence (IZhO17_subsequence)C++14
23 / 100
387 ms262144 KiB
#include<iostream> #include<vector> #include<algorithm> #include<cassert> #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]; int trace[N]; int maxx = 0; pair<int, int> f[MASK(20)]; 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]; maxx = max(a[i], maxx); } for(int i = 1; i <= n; i++) { cin >> k[i]; } if(n <= 5000) { vector<int> f(n + 1, 0); 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(f[i] < f[j] + 1) { 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()); cout << ans.size() << '\n'; for(int i = 0; i < (int)ans.size(); i++) cout << ans[i] << ' '; } else { int max_log = 0; while(maxx >= MASK(max_log)) max_log++; for(int i = 0; i < MASK(max_log); i++) f[i] = make_pair(0, -1); int p = -1; for(int i = 1; i <= n; i++) { trace[i] = -1; if(f[a[i]].first < 1) f[a[i]] = make_pair(1, i); for(int mask = 0; mask < MASK(max_log); mask++) if(__builtin_popcount(mask & a[i]) == k[i]) if(f[a[i]].first < f[mask].first + 1) { trace[i] = f[mask].second; f[a[i]] = make_pair(f[mask].first + 1, 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()); cout << ans.size() << '\n'; for(int i = 0; i < (int)ans.size(); i++) cout << ans[i] << ' '; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...