QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#655998#9249. Elimination Series Once Morehjxddl#WA 1ms5896kbC++201.3kb2024-10-19 10:45:122024-10-19 10:45:13

Judging History

你现在查看的是最新测评结果

  • [2024-10-19 10:45:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5896kb
  • [2024-10-19 10:45:12]
  • 提交

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'