QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#208042#6416. Classical Scheduling ProblemduckierWA 1ms5656kbC++142.9kb2023-10-09 04:14:112023-10-09 04:14:11

Judging History

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

  • [2023-10-09 04:14:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5656kb
  • [2023-10-09 04:14:11]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct node {
	int a;
	int b;
	int idx;
};

const int MAXN = 2e5 + 5;
int q, n, t, tot;
node topics[MAXN], sorted[MAXN];
auto cmp2 = [](int i1, int i2) { return topics[i1].a < topics[i2].a; };
set<int, decltype(cmp2)> usedl(cmp2), unusedl(cmp2), usedr(cmp2), unusedr(cmp2);

bool cmp(node n1, node n2) {
	if (n1.b == n2.b) {
		return n1.a < n2.a;
	}
	return n1.b < n2.b;
}

bool incm() {
	if (unusedr.empty()) {
		return false;
	}
	int minuu = *(unusedr.begin());
	tot += topics[minuu].a;
	usedr.insert(minuu);
	unusedr.erase(minuu);
	return true;
}

bool add(int x) {
	unusedl.insert(x);
	int maxu = *usedl.rbegin(), minuu = *unusedl.begin();
	if (topics[maxu].a > topics[minuu].a) {
		//replace with cheaper option
		usedl.insert(minuu);
		unusedl.erase(minuu);
		usedl.erase(maxu);
		unusedl.insert(maxu);
		tot += topics[minuu].a - topics[maxu].a;
	}
	//process right side
	if (usedr.find(x) != usedr.end()) {
		//is using this one
		usedr.erase(x);
		if (unusedr.empty()) {
			return false;
		}
		int minuu = *unusedr.begin();
		usedr.insert(minuu);
		unusedr.erase(minuu);
	}
	else {
		unusedr.erase(x);
	}
	return true;
}

bool test(int k) {
	int s = max(k, sorted[k].b);
	for (int i = 1; i <= s; i++) {
		unusedl.insert(sorted[i].idx);
	}
	for (int i = 1; i <= k; i++) {
		int minuu = *unusedl.begin();
		usedl.insert(minuu);
		unusedl.erase(minuu);
		tot += topics[minuu].a;
	}
	for (int i = s + 1; i <= n; i++) {
		unusedr.insert(sorted[i].idx);
	}
	int remaining = s - k;
	for (int i = 1; i <= remaining; i++) {
		if (unusedr.empty()) return false;
		int minuu = *unusedr.begin();
		usedr.insert(minuu);
		unusedr.erase(minuu);
		tot += topics[minuu].a;
	}
	if (tot <= t) return true;
	int c = s;
	for (int m = s; m <= n; m++) {
		while (c < n && sorted[c + 1].b <= m) {
			add(c + 1);
			c++;
			if (tot <= t) return true;
		}
		if (tot <= t) return true;
		incm();
		if (tot <= t) return true;
	}
	return false;
}

void reset() {
	tot = 0;
	usedl.clear();
	unusedl.clear();
	usedr.clear();
	unusedr.clear();
}

signed main() {
	cin >> q;
	while (q--) {
		cin >> n >> t;
		reset();
		for (int i = 1; i <= n; i++) {
			int x, y;
			cin >> topics[i].a >> topics[i].b;
			topics[i].idx = i;
			sorted[i] = topics[i];
		}
		sort(sorted + 1, sorted + n + 1, cmp);
		int lo = 0, hi = n;
		while (lo != hi) {
			reset();
			int mi = (lo + hi) / 2 + 1;
			if (test(mi)) {
				lo = mi;
			}
			else {
				hi = mi - 1;
			}
		}
		set<int> s;
		for (auto i = usedl.begin(); i != usedl.end(); i++) {
			s.insert(*i);
		}
		for (auto i = usedr.begin(); i != usedr.end(); i++) {
			s.insert(*i);
		}
		cout << lo << '\n';
		cout << s.size() << '\n';
		for (auto i = s.begin(); i != s.end(); i++) {
			cout << *i << ' ';
		}
		cout << '\n';
	}
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5656kb

input:

2
4 100
20 1
40 4
60 3
30 3
1 5
10 1

output:

2
3
1 2 4 
0
1
1 

result:

wrong answer too much time taken to learn the topics: 10 > 5 (test case 2)