이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define ll long long
#define dl double long
using namespace std;
const int NN = 2e6 + 7;
const int N = 1e6 + 7;
const int M = 22;
const int mod = 998244353;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
int a[N];
int k[N];
pair < int , int > d[N];
int p[N];
void solve1()
{
cin >> n;
for( int i = 1; i <= n; i++ ){
cin >> a[i];
}
for( int i = 1; i <= n; i++ ){
cin >> k[i];
}
if( n <= 5000 ){
int mx = 1;
for( int i = 1; i <= n; i++ ){
d[i].se = -1;
d[i].fi = 1;
for( int j = 1; j < i; j++ ){
if( d[j].fi + 1 > d[i].fi && __builtin_popcount(a[j] & a[i]) == k[i] ){
d[i].fi = d[j].fi + 1;
mx = max( mx , d[i].fi );
d[i].se = j;
}
}
}
int p = n;
for( int i = 1; i <= n; i++ ){
if( d[i].fi == mx )p = i;
}
vector < int > ans;
while( p != -1 ){
ans.push_back(p);
p = d[p].se;
}
reverse( ans.begin() , ans.end() );
cout << mx << "\n";
for( auto x : ans ){
cout << x << " ";
}
return;
}
pair < int , int > ans = {0 , 0};
for( int i = 1; i <= n; i++ ){
int mx = -1;
for( int j = 0; j < (1 << 8); j++ ){
if( __builtin_popcount( (a[i] & j) ) == k[i] ){
if( mx == -1 || d[j].fi + 1 > d[mx].fi ){
mx = j;
}
}
}
if( mx != -1 ){
if( d[a[i]].fi < d[mx].fi + 1 ){
p[i] = d[mx].se;
d[a[i]] = { d[mx].fi + 1 , i };
}
}else if( d[a[i]].fi == 0 )d[a[i]] = {1 , i};
if( d[a[i]].fi > ans.fi ){
ans = d[a[i]];
}
}
cout << ans.fi << "\n";
vector < int > v;
while( ans.se != 0 ){
v.push_back(ans.se);
ans.se = p[ans.se];
}
reverse( v.begin() , v.end() );
for( auto x : v )cout << x << " ";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
int cghf = 1;//cin >> cghf;
while( cghf-- ){
solve1();
}
}
# | 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... |