| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1269094 | raymoo_ | Longest beautiful sequence (IZhO17_subsequence) | C++17 | 0 ms | 0 KiB |
#pragma GCC optimize("O3") // Enable aggressive optimizations
#pragma GCC optimize("unroll-loops") // Unroll loops for potential performance gains
#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,sse4.1,sse4.2") // Target specific CPU features for further optimization
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define umap unordered_map
#define prq priority_queue
#define vect vector
#define rs resize
#define bend(v) v.begin(),v.end()
#define pob pop_back
#define pof pop_front
#define lwb lower_bound
#define upb upper_bound
#define pii pair<int,int>
#define nextl cout << '\n'
#define el '\n'
#define deb cout<<"\nok\n";return
#define ll long long
#define dbl long double
#define popcnt __builtin_popcount
#define ctz __builtin_ctz
#define FILE "ellencute"
const ll INF=902337203695775807, N=2e5+69, MOD=1e9+7;
void ffopen(){
if(fopen(FILE".inp", "r")){
freopen(FILE".inp", "r", stdin);
freopen(FILE".out", "w", stdout);
}else if(fopen("ellencute.inp", "r")){
freopen("ellencute.inp", "r", stdin);
freopen("ellencute.out", "w", stdout);
}
}
int pm(int a,const int b=1e9+7){return ((a%b)+b)%b;}
int sq(int x){return x*x;}
ll __lcm(ll a, ll b, const ll lim=LLONG_MAX){
if(a == -1 || b == -1)return -1;
ll g = __gcd(a,b);
if(b/g > lim/a)return -1;
return (a/g)*b;
}
int pc[(int)2e6], par[N];
void sol(){
int n;
cin >> n;
int a[n], k[n], dp[n];
fill(dp, dp+n, 1);
memset(par, -1, sizeof par);
for(int& i : a) cin >> i;
for(int& i : k) cin >> i;
for(int i=0;2e6>i;i++) pc[i] = popcnt(i);
int mx = 0;
map<int, vect<int>, greater<int>> fumo;
for(int idx=0;n>idx;idx++){
for(auto& i : fumo){
for(auto& j : i.se) if(pc[a[idx] & a[j]] == k[idx]){
dp[idx] = i.fi+1;
par[idx] = j;
break;
}
if(par[idx] != -1) break;
}
fumo[dp[idx]].eb(idx);
mx = max(mx, dp[idx]);
}
for(int i=n-1;i>=0;i--){
if(dp[i] == mx){
vect<int> ans;
for(;i>-1;i=par[i]) ans.eb(i);
cout << ans.size() << el;
reverse(bend(ans));
for(int i : ans) cout << i+1 << ' ';
return;
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ffopen();
int t=1;
//cin >> t;
while(t--)sol();
}
/*
...-%%%%%%%%%%%...
.:**#%=%%%%%+........-%%%%. .
.%%%%%%=-..%#. .#%%.
%%%+.. .: *%%.
.%%. :. :%%%%%:.
.%%. ... .: :: .=%%%.
..%%. #%#:%. : :.. =%%.
%%+..: .%*::::%-::::::-::::::.. .:-%%%%. .*%%..
.%# :.%:::::::%%%%%%%%%%%%%+...%%%+::::%#. .%%.
.%%. ..:.%=::::*%#***#%::::::::%%%%=:::::::%%. .%%.
=%%%...-%%%:::*%********%:::%%%****%::::::::%% .%-
.%::::%%***%=:%%**********%%********%:::::::=%-:. .%..
#%:::%#*****%%**********************%:::+%%%*%%-.: .::..%%.
.%%::%%*****==**==*****#************#%%%%#******%%..::::.. .%%.
.%%#%+%%***************##*+=+*==********************%%.:. .%%
.%%***%%****************#**==**==******==**+=+********%%%%%%%%% %%.
.#%#*********************%%**************++************%%::::::%* .%%%.
.%%***************#*****%%%****************************%%::::::%% .-%%%.
.#%***************#****%%--%*********%*****************%#::::-%%%%%%%%%%.
.%%**************#**%%%----%********%%**************#***#%%%#**%#******%*
.%%**************#%%%--.....%%*******%%**************#**********#%******%%.
.%%*************%%...........%%******%-%*************#***********%%*****%%.
.%%*************%%...%%%%%.....%%%%%%%.=%%%%%%%%##****#****##::::+%%*****%#
.%%************%%...%. %%.................%%%%-.....%*****#*****%%*****%%
.#%#*#****#****%%:::%- %%.................%. #-....%*****#*#####%#****%%.
.%%##****%%%**%%:::::##...................%= .%+:::%#*****#:####*%%****%%.
.+%%#**%%.#%%%%::::::........###+.:*##-....%%%:::::%*****##******%%****%%-
..%%*%%.......:::.......##..#*...#+..#*....:::::%******#*****##%%*****%%.
.%%%%%................#-##=--##+-+###-#....:::%******#:###*::%%#*****%%.
.%%****%%..............#----------------=*...#%#****##**##::#**%%*******%%.
.%%%%%*=+%%*...........#-----------------#.....#%%%%%%+:##*##:*%%*******%%%.
..:*%====%%%%........#-----------------#:.........%#********%%*****%%%%%%.
.%%=======*%%%%%%%.%%+----#-%------%%#.......%%%%::::::::%%==***#%###%%.
..%%=============+%%-:#%%%%-::%%%%%%::%%%%%%%%%=%%*******%%=====**%%###%%..
-%%%%%%%%%%%%%%%%+%.%+:+%::%::::%::%:::%%#%... .%%******%%%========#%####%%.
.%%++#############%%# ..%%.**%%#%%%%%%%#%***%. :%%*****%%%=+%%%%%%%%%%#####%%.
.%%++++*############*++% .%************#****%. #%*%%%%+++%%%%###############%%.
.+%%%%%%%%%%####+##########*+++++%%. .%**#**********#****% %%**%%%++++###################%:
=%%%%######################++++++++%%*%.-%%#***********#****% .%****%%+++++###################%%
.%%%#######################*%%%%%%%%.%%*#%+%###################%.%%***%%%+++++###################%%
*%%######################+#%%++++++%*. =%*%. .:%%%%########%%%%%%%%%#*#%.%%++#####################%%
.%%%#####################%%%%%+++++++%- %*#%%. .%%%*++++++*%%%....%%#####################%%*
%%######%%%%%#%%%%%######%%.%*+++++++%. %****#. .%%+++*+++++*++%%...=%%###################%%%.
%%%%%%%%#-=##%...%%######%%.%%+++++++%%..*%***#%%%%%. ..%+++++++++++++++%%...%%##################%%%.
.%:. .#%#####%%.%%+++++++++%. %*********%%%%%++++++++++++++++%%...%%##############%%%%..
:%#####%% .%%+++++++%% .%%**********%%++++++++++++++++%%.....%#########%%%%%% .
*%#####%%. .%%+++++++%%:. .%%********%%++++++++++++++++%%....%%%%%%%%%%%%*..
.%%##%%% .%%*+++++++%%. ..#%%%#****%%+++++++++++++++%%%%%% . .....
%%#%%%. .:%%%%%%%%%%%...-%. ......%%+++++++++++++%%.
..%%%. ... .%%%#%%%=:#%%%%%%%%*++++++%%%#
.-%%+. ... .%%%%%%%:.
*/