이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define log(x) (63^__builtin_clzll(x))
//#define endl '\n'
#define all(x) (x).begin() , (x).end()
pair<int, int> dp[(1 << 10) + 2][(1 << 10) + 2][11];
void solve() {
int n;
cin >> n;
vector<int> a(n), k(n);
for(int i = 0; i < n; ++i) cin >> a[i];
for(int i = 0; i < n; ++i) cin >> k[i];
int fullDown = (1 << 10) - 1, fullUp = (1 << 20) - 1 - fullDown, ans = 0, last = 0;
vector<int> prev(n, -1);
for(int i = 0; i < n; ++i) {
int mx = 1, up = ((fullUp & a[i]) >> 10), down = (fullDown & a[i]);
for(int reqUp = 0; reqUp < (1 << 10); ++reqUp) {
int common = __builtin_popcount((reqUp & up));
if(k[i] >= common) {
auto &state = dp[reqUp][down][k[i] - common];
if(state.first + 1 > mx) prev[i] = state.second;
mx = max(mx, state.first + 1);
}
}
if(mx > ans) last = i;
ans = max(ans, mx);
for(int reqDown = 0; reqDown < (1 << 10); ++reqDown) {
int common = __builtin_popcount((reqDown & a[i]));
dp[up][reqDown][common] = max(dp[up][reqDown][common], {mx, i});
}
}
vector<int> indices;
while(last != -1) {
indices.push_back(last);
last = prev[last];
}
assert(indices.size() == ans);
reverse(all(indices));
int ok = 1;
for(int j = 1; j < indices.size(); ++j)
if(__builtin_popcount(a[indices[j]] & a[indices[j - 1]]) != k[indices[j]]) ok = 0;
if(ok == 0) {
--ans;
indices.pop_back();
}
cout << ans << endl;
for(auto j : indices) cout << j + 1 << " ";
cout << endl;
return;
}
main() {
ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
/*
1 1 1 1
0 1 1 0
0 1 0 1
0 1 0 0
*/
컴파일 시 표준 에러 (stderr) 메시지
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from subsequence.cpp:1:
subsequence.cpp: In function 'void solve()':
subsequence.cpp:40:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
40 | assert(indices.size() == ans);
| ~~~~~~~~~~~~~~~^~~~~~
subsequence.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int j = 1; j < indices.size(); ++j)
| ~~^~~~~~~~~~~~~~~~
subsequence.cpp: At global scope:
subsequence.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
58 | main() {
| ^~~~
# | 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... |