#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
const int nmax = 2e5 + 100;
const ll oo = 1e18, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 7;
#define pii pair<int, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;
int n, k[nmax], a[nmax];
namespace subtask2{
int dp[nmax];
bool check(){
if(n <= 5e3) return 1;
return 0;
}
void sol(){
int ans = 0;
for(int i = 1; i <= n; ++i){
dp[i] = 1;
for(int j = 1; j < i; ++j){
int x = __builtin_popcount(a[i] & a[j]);
// cout << x << ' ';
if(x == k[i]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
// cout << "\n";
ans = max(ans, dp[i]);
}
cout << ans << "\n";
vector<int> v;
for(int i = 1; i <= n; ++i){
if(dp[i] == ans){
int id = i;
while(ans > 0){
v.push_back(id);
for(int j = 1; j < id; ++j){
int x = __builtin_popcount(a[id] & a[j]);
// cout << x << ' ';
if(x == k[id] && dp[id] == dp[j] + 1){
id = j;
break;
}
}
--ans;
}
}
}
reverse(v.begin(), v.end());
for(auto p : v) cout << p << ' ';
}
}
namespace subtask3{
int trace[nmax];
bool check(){
if(*max_element(a + 1, a + 1 + n) < (1 << M)) return 1;
return 0;
}
int gg[nmax];
void sol(){
int ans = 0;
vector<pii> dp, f;
dp.resize(1 << M);
f.resize(1 << M);
for(int i = 1; i <= n; ++i){
for(int msk = 0; msk < (1 << M); ++msk){
int x = __builtin_popcount(msk & a[i]);
if(x == k[i]){
int &cur = dp[a[i]].fi;
if(cur < f[msk].fi + 1){
cur = f[msk].fi + 1;
trace[i] = f[msk].se;
}
}
}
dp[a[i]].fi = max(dp[a[i]].fi, 1);
for(int msk = 0; msk < (1 << M); ++msk){
if(dp[msk].fi != f[msk].fi){
dp[msk].se = i;
}
gg[i] = max(gg[i], dp[msk].fi);
}
f = dp;
}
int id = 0;
for(int i = 1; i <= n; ++i){
if(gg[id] < gg[i]){
id = i;
}
}
cout << gg[id] << "\n";
vector<int> v;
while(id > 0){
v.push_back(id);
id = trace[id];
}
reverse(v.begin(), v.end());
for(auto p : v) cout << p << ' ';
// for(int )
}
}
namespace subtask4{
pii dp[1 << M][21][1 << M];
int f[nmax], trace[nmax];
int bit(int msk, int x){
return msk >> x & 1;
}
void sol(){
for(int i = 1; i <= n; ++i){
f[i] = 1;
int pre = 0, suf = 0;
for(int j = 0; j < M; ++j){
if(bit(a[i], j)) pre |= 1 << j;
}
for(int j = M; j < 2 * M; ++j){
if(bit(a[i], j)) suf |= 1 << j;
}
for(int msk = 0; msk < (1 << M); ++msk){
int x = __builtin_popcount(suf& msk);
if(x <= k[i]){
auto cur = dp[pre][k[i] - x][msk];
if(f[i] < cur.fi + 1){
f[i] = cur.fi + 1;
trace[i] = cur.se;
}
}
}
for(int msk = 0; msk < (1 << M); ++msk){
int x = __builtin_popcount(msk & pre);
auto &cur = dp[msk][x][suf];
if(cur.fi < f[i]) cur = {f[i], i};
}
}
int id = 0;
for(int i = 1; i <= n; ++i){
if(f[id] < f[i]){
id = i;
}
}
cout << f[id] << "\n";
vector<int> v;
while(id > 0){
v.push_back(id);
id = trace[id];
}
reverse(v.begin(), v.end());
for(auto p : v) cout << p << ' ';
}
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.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];
if(subtask2::check()) return subtask2::sol(), 0;
if(subtask3::check()) return subtask3::sol(), 0;
subtask4::sol();
}
/*
4
1 2 3 4
10 0 1 0
5
5 3 5 3 5
10 1 20 1 20
*/
Compilation message
uzastopni.cpp: In function 'void subtask3::sol()':
uzastopni.cpp:73:13: warning: unused variable 'ans' [-Wunused-variable]
73 | int ans = 0;
| ^~~
uzastopni.cpp: At global scope:
uzastopni.cpp:163:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
163 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
2548 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 11 |
Incorrect |
38 ms |
2712 KB |
Output isn't correct |
| 12 |
Incorrect |
38 ms |
2652 KB |
Output isn't correct |
| 13 |
Incorrect |
38 ms |
2652 KB |
Output isn't correct |
| 14 |
Incorrect |
39 ms |
2652 KB |
Output isn't correct |
| 15 |
Incorrect |
40 ms |
2652 KB |
Output isn't correct |
| 16 |
Incorrect |
38 ms |
2720 KB |
Output isn't correct |
| 17 |
Incorrect |
38 ms |
2652 KB |
Output isn't correct |
| 18 |
Incorrect |
38 ms |
2708 KB |
Output isn't correct |
| 19 |
Incorrect |
38 ms |
2652 KB |
Output isn't correct |
| 20 |
Incorrect |
38 ms |
2704 KB |
Output isn't correct |
