QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #497058 | #7942. $K$ Subsequences | deepthought | WA | 34ms | 3636kb | C++23 | 3.5kb | 2024-07-28 18:33:57 | 2024-07-28 18:33:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct CompareSecond {
bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) {
return p1.second > p2.second; // min-heap based on the second element
}
};
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
for(int tt = 1; tt <= tc; tt++) {
int n, k;
cin >> n >> k;
vector <int> a(n);
bool pl = true;
int cnt = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
if(a[i] == 1) pl = false;
if(a[i] == 1) cnt++;
}
if(pl == true) {
for(int i = 0; i < n; i++) cout << 1 << " ";
cout << '\n';
continue;
}
// if(tt == 14722) assert(a[7] == - 1);
// k = 2
// 7 tane 1
// 3 tane 0
// Array: [1, 1, 1, - 1, -1, -1, 1, 1, 1, 1]
// 000011111
// lo last 0, high first 1
int lo = 0;
int hi = n;
while((hi - lo) > 1) {
int mid = lo + (hi - lo) / 2;
priority_queue<pair<int, int>, vector<pair<int, int>>, CompareSecond> pos;
stack <pair<int, int>> neg;
for(int i = k; i >= 1; i--) {
pos.push({i, 0});
}
bool ok = true;
for(int i = 0; i < n; i++) {
if(a[i] == 1) {
if(pos.empty()) {ok = false; break;}
auto [x, y] = pos.top();
pos.pop();
if(y + 1 == mid) neg.push({x, y + 1});
else pos.push({x, y + 1});
}
else if(a[i] == - 1) {
if(neg.empty()) {
if(pos.empty()) {ok = false; break;}
auto [x, y] = pos.top();
pos.pop();
pos.push({x, max(y - 1, 0)});
}
else {
auto [x, y] = neg.top();
neg.pop();
assert(y > 0);
assert(y == mid);
pos.push({x, y - 1});
}
}
}
if(ok) {
hi = mid;
}
else {
lo = mid;
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, CompareSecond> pos;
stack <pair<int, int>> neg;
for(int i = k; i >= 1; i--) {
pos.push({i, 0});
}
int mid = hi;
for(int i = 0; i < n; i++) {
if(a[i] == 1) {
auto [x, y] = pos.top();
cout << x << " ";
pos.pop();
if(y + 1 == mid) neg.push({x, y + 1});
else pos.push({x, y + 1});
}
else if(a[i] == - 1) {
if(neg.empty()) {
auto [x, y] = pos.top();
cout << x << " ";
pos.pop();
pos.push({x, max(y - 1, 0)});
}
else {
auto [x, y] = neg.top();
cout << x << " ";
neg.pop();
assert(y > 0);
pos.push({x, y - 1});
}
}
}
cout << '\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
5 3 2 1 -1 1 4 2 -1 1 1 -1 7 3 1 1 1 1 1 1 1 10 3 1 1 1 1 -1 -1 1 1 1 1 12 4 1 1 1 1 -1 -1 -1 -1 1 1 1 1
output:
2 2 1 2 1 2 2 3 2 1 3 2 1 3 3 2 1 3 3 2 2 3 1 2 4 2 3 1 1 3 2 4 1 2 3 4
result:
ok Correct (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 34ms
memory: 3572kb
input:
18434 10 1 -1 1 1 -1 -1 1 -1 -1 1 1 10 2 -1 -1 -1 1 1 -1 1 1 1 1 10 2 1 -1 -1 -1 -1 1 1 -1 1 1 10 7 1 1 -1 1 -1 1 1 -1 -1 1 9 1 -1 1 -1 1 1 -1 1 -1 1 8 1 -1 -1 -1 -1 1 1 -1 -1 10 3 -1 -1 -1 1 1 1 1 -1 -1 -1 9 1 1 -1 -1 1 -1 -1 -1 -1 -1 10 10 -1 1 1 1 1 1 1 1 1 1 10 4 -1 1 -1 1 -1 1 1 -1 1 1 9 3 1 1 ...
output:
1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 1 2 1 2 2 1 1 1 1 1 2 2 1 2 7 5 5 2 2 1 5 5 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 3 2 1 3 3 2 2 1 1 1 1 1 1 1 1 1 10 8 4 1 10 2 5 3 6 9 4 2 2 1 1 4 2 2 3 1 3 2 2 3 1 1 2 2 3 4 2 2 3 1 2 2 2 7 5 2 1 7 3 6 4 4 4 6 6 4 1 1 6 4 1 1 1 1 1 1 1 1 1 1 1 3...
result:
wrong answer Jury found better answer than participant (test case 76)