이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define getbit(x,i) ((x >> i)&1)
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e5 + 7
using namespace std;
int n;
int dp[maxn], a[maxn];
int L[(1 << 10) + 1][(1 << 10) + 1][11];
int p[maxn];
void Trace_Back(int id)
{
vector<int> ans = {id};
int pre = id;
fid(i, id - 1, 1)
{
if(cntbit(a[i] & a[pre]) == p[pre] && (dp[i] == dp[pre] - 1)){
ans.push_back(i);
pre = i;
}
}
fid(i, ans.size() - 1, 0) cout << ans[i] << " ";
exit(0);
}
tuple<int, int> dcm(int x)
{
int l = 0, r = 0;
fi(i, 1, 10) if(getbit(x, i - 1)) l |= (1 << (i - 1));
fi(i, 11, 20) if(getbit(x, i - 1)) r |= (1 << (i - 10 - 1));
return {l, r};
}
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
fi(i, 1, n) cin >> a[i];
fi(i, 1, n) cin >> p[i];
int ans = 0;
fi(i, 1, n)
{
dp[i] = 1;
int Left, Right;
tie(Left, Right) = dcm(a[i]);
fi(l, 0, (1 << 10) - 1) dp[i] = max(dp[i], L[l][Right][p[i] - cntbit(l & Left)] + 1);
fi(r, 0, (1 << 10) - 1) L[Left][r][cntbit(r & Right)] = max(L[Left][r][cntbit(r & Right)], dp[i]);
ans = max(ans, dp[i]);
}
cout << ans << '\n';
fi(i, 1, n) if(dp[i] == ans) Trace_Back(i);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
subsequence.cpp: In function 'std::tuple<int, int> dcm(int)':
subsequence.cpp:37:33: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
37 | fi(i, 1, 10) if(getbit(x, i - 1)) l |= (1 << (i - 1));
| ~~^~~
subsequence.cpp:5:28: note: in definition of macro 'getbit'
5 | #define getbit(x,i) ((x >> i)&1)
| ^
subsequence.cpp:38:34: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
38 | fi(i, 11, 20) if(getbit(x, i - 1)) r |= (1 << (i - 10 - 1));
| ~~^~~
subsequence.cpp:5:28: note: in definition of macro 'getbit'
5 | #define getbit(x,i) ((x >> i)&1)
| ^
# | 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... |