QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225986#6553. Shared Memory SwitchGiga_CronosRE 1ms3524kbC++232.2kb2023-10-25 14:04:462023-10-25 14:04:46

Judging History

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

  • [2023-10-25 14:04:46]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3524kb
  • [2023-10-25 14:04:46]
  • 提交

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;
	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);
				pq.erase(pii(*vs[x].begin(), i));
				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);
				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: 3460kb

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

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: 1ms
memory: 3524kb

input:

0 0

output:

0

result:

ok n=0

Test #4:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

0 1

output:

0

result:

ok n=0

Test #5:

score: -100
Runtime Error

input:

3 0
1 -1 2

output:


result: