QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#785575 | #9786. Magical Bags | orz_z | WA | 0ms | 3584kb | C++14 | 1.2kb | 2024-11-26 18:20:15 | 2024-11-26 18:20:16 |
Judging History
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'