QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491284 | #6553. Shared Memory Switch | pandapythoner | WA | 45ms | 13520kb | C++23 | 2.1kb | 2024-07-25 18:23:46 | 2024-07-25 18:23:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
const ll inf = 1e18;
mt19937 rnd(234);
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, B;
cin >> n >> B;
vector<vector<pair<int, int>>> starts(n);
vector<int> a(n);
int t = 0;
rep(i, n) cin >> a[i];
rep(i, n) {
if (a[i] == -1) {
t += 1;
} else {
starts[a[i] - 1].push_back(make_pair(t, i));
}
}
vector<int> ends(n, -1);
for (int q = 0; q < n; q += 1) {
stack<int> s;
int j = 0;
int t = 0;
while (j < (int)starts[q].size() or !s.empty()) {
if (s.empty()) {
t = starts[q][j].first;
}
while (j < (int)starts[q].size() and starts[q][j].first == t) {
s.push(starts[q][j].second);
j++;
}
if (!s.empty()) {
int k = s.top();
ends[k] = t;
s.pop();
}
}
}
set<pair<int, int>> st;
vector<int> result;
t = 0;
for (int i = 0; i < n; i += 1) {
if (ends[i] == -1) {
t += 1;
while (!st.empty() and st.begin()->first < t) {
result.push_back(st.begin()->second);
st.erase(st.begin());
}
continue;
}
st.insert(make_pair(ends[i], i));
if ((int)st.size() > B) {
auto it = prev(st.end());
st.erase(it);
}
}
while (!st.empty()) {
result.push_back(st.begin()->second);
st.erase(st.begin());
}
sort(all(result));
cout << (int)result.size() << "\n";
for (auto x : result) {
cout << x + 1 << " ";
}
cout << "\n";
return 0;
}
/*
14 5
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
14 4
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
14 5 1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
output:
9 1 2 3 4 5 8 10 12 14
result:
ok n=14
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
14 4 1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
output:
8 1 2 3 4 8 10 12 14
result:
ok n=14
Test #3:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
0 0
output:
0
result:
ok n=0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
0 1
output:
0
result:
ok n=0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
3 0 1 -1 2
output:
0
result:
ok n=3
Test #6:
score: 0
Accepted
time: 45ms
memory: 13520kb
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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 44077 44078 44079 44080 44081 44082 44083 44084 44085 44086 44087 44088 44089 44090 44091 44092 44093 44094 44095 44096
result:
ok n=200000
Test #7:
score: 0
Accepted
time: 40ms
memory: 12492kb
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
Wrong Answer
time: 28ms
memory: 10912kb
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 ...
output:
99977 3 5 6 8 9 10 12 14 15 16 19 20 21 25 27 33 40 42 43 45 46 47 51 52 53 55 56 57 58 60 61 62 64 67 69 71 72 73 74 77 79 83 86 88 90 91 94 95 99 100 102 103 104 105 109 111 112 113 114 119 120 122 124 125 126 129 131 132 133 134 136 141 144 146 148 149 153 154 155 157 160 161 165 166 167 168 169 ...
result:
wrong answer Buffer overflowed