QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226003#6553. Shared Memory SwitchGiga_CronosRE 98ms37408kbC++232.3kb2023-10-25 14:22:422023-10-25 14:22:42

Judging History

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

  • [2023-10-25 14:22:42]
  • 评测
  • 测评结果:RE
  • 用时:98ms
  • 内存:37408kb
  • [2023-10-25 14:22:42]
  • 提交

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();
				int v = *vs[x].begin();
				ans.push_back(p);
				if (pq.count(pii(v, x))) {
					pq.erase(pii(v, x));
				}
				vs[x].erase(v);
				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);
			if (!vs[x].empty() && *vs[x].rbegin() < v) {
				pq.erase(pii(*vs[x].rbegin(), x));
				pq.insert(pii(v, x));
			}
			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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

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: 3588kb

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: 3888kb

input:

0 0

output:

0

result:

ok n=0

Test #4:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

0 1

output:

0

result:

ok n=0

Test #5:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

3 0
1 -1 2

output:

0

result:

ok n=3

Test #6:

score: 0
Accepted
time: 98ms
memory: 37408kb

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: 50ms
memory: 31340kb

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 ...

output:


result: