QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#655998 | #9249. Elimination Series Once More | hjxddl# | WA | 1ms | 5896kb | C++20 | 1.3kb | 2024-10-19 10:45:12 | 2024-10-19 10:45:13 |
Judging History
answer
// Coded by hjxddl
#include <bits/stdc++.h>
#define ll long long
#define db double
#define mid (l + r >> 1)
const int N = 2e6 + 5;
int sum[N << 2];
int a[N], pos[N];
int n, n1, k;
int query(int k1, int ans = n, int x = 1, int l = 1, int r = n1) {
if (sum[x] <= k && r - l <= k1 - 1)
return ans;
if (pos[k1] <= mid)
return query(k1, ans - 1, x << 1, l, mid);
else
return query(k1, ans - 1, x << 1 | 1, mid + 1, r);
}
void change(int k1, int x = 1, int l = 1, int r = n1) {
if (l == r) {
sum[x] = 1;
return;
}
if (k1 <= mid)
change(k1, x << 1, l, mid);
else
change(k1, x << 1 | 1, mid + 1, r);
sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
void solve() {
std::cin >> n >> k;
n1 = 1 << n;
for (int i = 1; i <= n1; i++) {
std::cin >> a[i];
pos[a[i]] = i;
}
// build();
std::stack<int> ans;
for (int i = n1; i >= 1; i--) {
ans.push(query(i));
change(pos[i]);
}
while (ans.size()) {
std::cout << ans.top() << " ";
ans.pop();
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0), std::cout.tie(0);
int t = 1;
// std::cin >> t;
while (t--) {
solve();
}
std::cout << std::flush;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5676kb
input:
2 1 1 2 3 4
output:
0 1 1 2
result:
ok 4 number(s): "0 1 1 2"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5896kb
input:
3 5 2 4 7 5 3 8 6 1
output:
0 1 1 2 2 2 2 3
result:
wrong answer 1st numbers differ - expected: '1', found: '0'