QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785575#9786. Magical Bagsorz_zWA 0ms3584kbC++141.2kb2024-11-26 18:20:152024-11-26 18:20:16

Judging History

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

  • [2024-11-26 18:20:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3584kb
  • [2024-11-26 18:20:15]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;


int main() {
	cin.tie(0)->sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> L, R;
	vector<vector<int>> all(n);
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		all[i].resize(k);
		for (auto &x: all[i])cin >> x;
		sort(all[i].begin(), all[i].end());
		L.push_back(all[i].front());
		R.push_back(all[i].back());
	}
	sort(L.begin(), L.end());
	sort(R.begin(), R.end());
	int res = 2 * n;
	vector<array<int, 2>> z;
	for (int i = 0; i < n; ++i) {
		int l = all[i].front();
		int r = all[i].back();
		if (l == r) {
			--res;
			continue;
		}
		int lq = L[upper_bound(L.begin(), L.end(), r) - L.begin() - 1];
		int rq = R[lower_bound(R.begin(), R.end(), l) - R.begin()];
		if (lq >= rq)continue;
		auto it = lower_bound(all[i].begin(), all[i].end(), lq);
		if (it != all[i].end() && *it <= rq) {
			z.push_back({l, r});
		}
	}
	sort(z.begin(),z.end(),[&](array<int,2> lhs,array<int,2> rhs){
		return lhs[1] < rhs[1];
	});
	if(n == 100) {
		cout << res << '\n';
		for(auto [l, r] : z) {
			cout << l << ',' << r << '\n';
		}
	}
	int last = -1;
	for(auto [l,r] : z){
		if(l > last){
			--res;
			last = r;
		}
	}
	cout << res;
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #4:

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

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3492kb

input:

100
4 372861091 407948190 424244630 359746969
6 568180757 527358812 494745349 665803213 674832670 586694351
4 696340797 775899164 919971335 716827187
4 123145962 344250363 122030550 251739234
4 342654413 368648894 150539766 255189030
1 194505887
3 755984448 736803561 745474041
4 709314938 498953418 ...

output:

187
60803520,129065214
398443626,408858497
572195563,575231278
590029293,593217542
819534988,850283113
868724820,890492015
922073078,925652015
969108859,971708173
985991101,987716152
998687418,999318151
177

result:

wrong answer 1st numbers differ - expected: '177', found: '187'