QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#225998 | #6553. Shared Memory Switch | Giga_Cronos | RE | 96ms | 37492kb | C++23 | 2.2kb | 2023-10-25 14:18:34 | 2023-10-25 14:18:35 |
Judging History
answer
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ld> pdd;
typedef pair<int, int> pii;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, b;
cin >> n >> b;
if (b == 0) {
cout << "0\n";
return 0;
}
vector<int> a(n);
vector<int> ini(n);
vector<vector<int>> pos(n);
set<int> avs;
int cm1 = 0;
for (int i = 0; i < n; i++) {
cin >> ini[i];
if (ini[i] == -1) {
vector<int> to_er;
for (auto x : avs) {
a[pos[x].back()] = cm1;
pos[x].pop_back();
if (pos[x].empty())
to_er.push_back(x);
}
for (auto x : to_er)
avs.erase(x);
cm1++;
} else {
ini[i]--;
pos[ini[i]].push_back(i);
if (pos[ini[i]].size() == 1)
avs.insert(ini[i]);
}
}
for (int i = 0; i < n; i++) {
reverse(all(pos[i]));
for (int j = 0; j < pos[i].size(); j++)
a[pos[i][j]] = cm1 + j;
}
avs.clear();
set<pii, greater<pii>> pq;
vector<set<int>> pos2(n);
vector<set<int>> vs(n);
vector<int> ans;
int act_sz = 0;
for (int i = 0; i < n; i++) {
if (ini[i] == -1) {
vector<int> to_er;
for (auto x : avs) {
int p = *pos2[x].begin();
ans.push_back(p);
if (pq.count(pii(*vs[x].begin(), x))) {
pq.erase(pii(*vs[x].begin(), x));
}
vs[x].erase(vs[x].begin());
pos2[x].erase(p);
if (pos2[x].empty()) {
to_er.push_back(x);
}
act_sz--;
}
for (auto x : to_er)
avs.erase(x);
} else {
if (act_sz == b) {
auto xx = *pq.begin();
int x = xx.second;
vs[x].erase(*vs[x].rbegin());
pos2[x].erase(*pos2[x].begin());
pq.erase(xx);
if (pos2[x].empty())
avs.erase(x);
else
pq.insert(pii(*vs[x].rbegin(), *pos2[x].begin()));
act_sz--;
}
int x = ini[i];
int v = a[i];
pos2[x].insert(i);
vs[x].insert(v);
if (pos2[x].size() == 1) {
avs.insert(x);
pq.insert(pii(v, x));
}
act_sz++;
}
}
for (int i = 0; i < n; i++)
for (auto x : pos2[i])
ans.push_back(x);
sort(all(ans));
cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++)
cout << ans[i] + 1 << " \n"[i + 1 == ans.size()];
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
14 5 1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
output:
9 2 3 4 5 6 8 10 12 14
result:
ok n=14
Test #2:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
14 4 1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
output:
8 2 3 5 6 8 10 12 14
result:
ok n=14
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
0 0
output:
0
result:
ok n=0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
0 1
output:
0
result:
ok n=0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
3 0 1 -1 2
output:
0
result:
ok n=3
Test #6:
score: 0
Accepted
time: 96ms
memory: 37492kb
input:
200000 20 192797 145760 146491 109352 168621 58673 57243 7936 79733 3190 191130 169391 178004 120789 25556 56547 72241 59274 101245 129056 125785 138556 70154 63360 96036 73373 168059 46716 197905 106279 113884 190286 56438 128423 151368 193658 15613 17963 26833 136697 62679 188745 4515 151940 67745...
output:
40 4268 5330 6376 9098 10382 11694 12237 13683 17213 22874 23170 26161 27444 28617 32488 35694 41987 42225 42437 44075 58853 59286 92139 105840 111333 133100 135041 135848 136878 141593 146610 146694 147170 148517 156145 158331 168638 171024 178343 200000
result:
ok n=200000
Test #7:
score: 0
Accepted
time: 48ms
memory: 31360kb
input:
200000 20 -1 -1 185081 -1 -1 34870 174269 47583 86208 69115 153529 101705 -1 -1 161748 11940 -1 -1 -1 191433 191546 -1 -1 108421 155301 -1 16678 -1 -1 -1 -1 179950 -1 169577 46923 -1 -1 -1 130194 -1 128371 -1 104684 -1 133162 170545 198827 -1 -1 72240 -1 -1 -1 110876 -1 -1 -1 80829 -1 84239 129224 -...
output:
100583 3 6 7 8 9 10 11 12 15 16 20 21 24 25 27 32 34 35 39 41 43 45 46 47 50 54 58 60 61 65 68 69 70 72 73 75 77 78 79 83 86 87 88 90 91 94 95 97 99 102 103 106 107 108 110 113 114 115 116 117 118 120 121 123 124 125 126 128 130 131 133 134 137 140 141 142 143 146 147 148 149 150 151 152 153 154 161...
result:
ok n=200000
Test #8:
score: -100
Runtime Error
input:
200000 20 -1 -1 9380 -1 9380 9380 -1 9380 9380 9380 -1 9380 -1 9380 9380 9380 -1 -1 9380 9380 9380 -1 -1 -1 9380 -1 9380 -1 -1 -1 -1 -1 9380 -1 -1 -1 -1 -1 -1 9380 -1 9380 9380 -1 9380 9380 9380 -1 -1 -1 9380 9380 9380 -1 9380 9380 9380 9380 -1 9380 9380 9380 -1 9380 -1 -1 9380 -1 9380 -1 9380 9380 ...