이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 1e6 + 2;
const ll inf = 3e18;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
template <typename T> void vout(T s){cout << s << endl;exit(0);}
ll Dp[MAXN], Wh[MAXN];
int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);
ll n;
cin >> n;
vector <ll> 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];
vector <ll> dp(n + 1), pr(n + 1);
if(n <= 5000){
for(int i = 1; i <= n; i++){
dp[i] = 1;
pr[i] = 0;
for(int j = 1; j < i; j++)if(__builtin_popcountll(a[i] & a[j]) == k[i]){
if(dp[i] < dp[j] + 1){
dp[i] = dp[j] + 1;
pr[i] = j;
}
}
}
ll Mx = *max_element(dp.begin() + 1, dp.end());
cout << Mx << "\n";
for(int i = 1; i <= n; i++)if(dp[i] == Mx){
ll x = i;
vector <ll> ans;
while(x){
ans.p_b(x);
x = pr[x];
}
reverse(all(ans));
for(auto i : ans)cout << i << " ";
cout << "\n";
return 0;
}
}
for(int i = 1; i <= n; i++){
dp[i] = 1;
pr[i] = 0;
for(int j = 1; j < pw(8); j++)if(__builtin_popcountll(a[i] & j) == k[i]){
if(dp[i] < Dp[j] + 1){
dp[i] = Dp[j] + 1;
pr[i] = Wh[j];
}
}
if(Dp[a[i]] < dp[i]){
Dp[a[i]] = dp[i];
Wh[a[i]] = i;
}
}
ll Mx = *max_element(dp.begin() + 1, dp.end());
cout << Mx << "\n";
for(int i = 1; i <= n; i++)if(dp[i] == Mx){
ll x = i;
vector <ll> ans;
while(x){
ans.p_b(x);
x = pr[x];
}
reverse(all(ans));
for(auto i : ans)cout << i << " ";
cout << "\n";
return 0;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |