제출 #518941

#제출 시각아이디문제언어결과실행 시간메모리
518941shmadLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6009 ms4340 KiB
    #pragma GCC optimize("O3", "Ofast", "unroll-loops")
    #pragma GCC target("sse", "sse2", "sse3", "sse4", "avx2", "bmi", "bmi2", "lzcnt", "popcnt") 
     
    #include <bits/stdc++.h>
         
        #define int long long
        #define vt vector
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define sz(x) (int)(x).size()
        #define ff first
        #define ss second
        #define dbg(x) cerr << #x << " = " << x << '\n'
         
        using namespace std;
        using ll = long long;
        using pii = pair<int, int>;
        using vvi = vt< vt<int> >;
         
        const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
        const double eps = 1e-6;
         
        int dp[N], p[N];
         
        void solve () {
        	int n;
        	cin >> n;
        	vt<int> a(n + 1), k(n + 1);
        	for (int i = 1; i <= n; i++) cin >> a[i];
        	for (int i = 1; i <= n; i++) cin >> k[i];
        	int res = 0, ps = 0;
        	for (int i = 1; i <= n; i++) {
        		dp[i] = 1;
        		for (int j = 1; j < i; j++) {
        			if (__builtin_popcount(a[i] & a[j]) != k[i]) continue;
        			if (dp[i] < dp[j] + 1) {
        				dp[i] = dp[j] + 1;
        				p[i] = j;
        			}
        		}
        		if (dp[i] > res) res = dp[i], ps = i;
        	}
        	cout << res << '\n';
        	vt<int> ans;
        	while (ps) {
        		ans.pb(ps);
        		ps = p[ps];
        	}
        	reverse(all(ans));
        	for (auto x: ans) cout << x << ' ';
        	cout << '\n';
        }
         
        bool testcases = 0;
                          
        signed main() {
            cin.tie(0) -> sync_with_stdio(0);
            int test = 1;
            if (testcases) cin >> test;
            for (int cs = 1; cs <= test; cs++) {
                solve();
            }
        }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...