이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Bismillahir-Rahmanir-Rahim
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2")
#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <long double, long double>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)
using namespace std;
const int N = 1e5 + 7;
const int M = 1e5 + 7;
const int maxA = 1e5 + 7;
const int inf = 1e9 + 7;
const ll INF = 2e18 + 7;
const int MOD = 998244353;
const ld eps = 1e-9;
pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start = clock();
//#define int long long
pii dp[N];
int n, a[N], b[N], pr[N];
void subtask12() {
int mx = 0, pos = 0;
for (int i = 1;i <= n;i++) {
dp[i] = {1, i};
for (int j = 1;j < i;j++) {
if (bpop(a[i] & a[j]) == b[i]) {
//cout << i << ' ' << j << ':' << dp[j].x + 1 << '\n';
if (dp[j].x + 1 > dp[i].x)dp[i] = {dp[j].x + 1, i}, pr[i] = j;
}
}
if (dp[i].x > mx)mx = dp[i].x, pos = i;
}
cout << mx << '\n';
vector <int> ans;
while (pos != 0)ans.pb(pos), pos = pr[pos];
reverse(all(ans));
for (auto i : ans)cout << i << ' ';
}
void solve() {
cin >> n;
for (int i = 1;i <= n;i++)cin >> a[i];
for (int i = 1;i <= n;i++)cin >> b[i];
if (n <= 5000)subtask12(), exit(0);
int mx = 0, pos = 0;
for (int i = 1;i <= n;i++) {
//cout << i << ":\n";
pii val = {1, 0};
for (int x = 0;x < (1ll << 8);x++) {
if (bpop(x & a[i]) == b[i]) {
//if (dp[x] > dp[a[i]])cout << x << ':' << dp[x].x << ' ' << dp[x].y << '\n';
val = max(val, {dp[x].x + 1, dp[x].y});
}
}
dp[a[i]] = max(dp[a[i]], val);
pr[i] = dp[a[i]].y, dp[a[i]].y = i;
if (dp[a[i]].x > mx)mx = dp[a[i]].x, pos = i;
}
cout << mx << '\n';
vector <int> ans;
while (pos != 0)ans.pb(pos), pos = pr[pos];
reverse(all(ans));
for (auto i : ans)cout << i << ' ';
}
signed main() {
//srand(time(NULL));
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("subsequence.in", "r", stdin);
//freopen("subsequence.out", "w", stdout);
int test = 1;
//cin >> test;
for (int t = 1;t <= test;t++) {
//cout << "Case " << t << ": ";
solve();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
subsequence.cpp:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
4 | #pragma comment(linker, "/stack:200000000")
|
# | 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... |