Task: | Education |
Sender: | Hannes Ihalainen |
Submission time: | 2017-10-31 19:00:47 +0200 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.04 s | details |
#3 | ACCEPTED | 0.05 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.04 s | details |
#6 | ACCEPTED | 0.06 s | details |
#7 | ACCEPTED | 0.05 s | details |
#8 | ACCEPTED | 0.03 s | details |
#9 | ACCEPTED | 0.05 s | details |
#10 | ACCEPTED | 0.08 s | details |
#11 | ACCEPTED | 0.03 s | details |
#12 | ACCEPTED | 0.06 s | details |
#13 | ACCEPTED | 0.04 s | details |
#14 | ACCEPTED | 0.05 s | details |
#15 | ACCEPTED | 0.04 s | details |
#16 | ACCEPTED | 0.05 s | details |
#17 | ACCEPTED | 0.04 s | details |
#18 | ACCEPTED | 0.04 s | details |
Code
#include <iostream> #include <vector> #include <algorithm> #include <set> #define F first #define S second #define MP make_pair using namespace std; int n, m; int s[5050]; int p[5050]; int r[5050]; vector<pair<pair<int, int>, int> > nn; set<pair<int, int> > rents; int ans[5050]; int main(){ cin >> n >> m; for (int i=0; i<n; ++i) cin >> s[i]; for (int i=0; i<m; ++i) cin >> p[i]; for (int i=0; i<m; ++i) cin >> r[i]; for (int i=0; i<n; ++i){ nn.push_back(MP(MP(s[i], 0), i)); } for (int i=0; i<m; ++i){ nn.push_back(MP(MP(p[i], 1), i)); } sort(nn.begin(), nn.end()); for (int i=nn.size()-1; i>=0; --i){ if (nn[i].F.S==0){ if (rents.size()==0){ cout << "impossible\n"; return 0; }else{ ans[nn[i].S]=rents.begin()->S; rents.erase(rents.begin()); } }else{ rents.insert(MP(r[nn[i].S], nn[i].S)); } } for (int i=0; i<n; ++i){ cout << (ans[i]+1) << " "; } cout << "\n"; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
2 3 1 2 2 1 2 1 1 2 |
correct output |
---|
2 1 |
user output |
---|
2 1 |
Test 2
Verdict: ACCEPTED
input |
---|
100 400 405 604 662 507 209 320 336 94... |
correct output |
---|
183 205 248 236 150 50 169 42 ... |
user output |
---|
183 205 248 236 150 50 169 42 ... |
Test 3
Verdict: ACCEPTED
input |
---|
100 400 596 494 947 89 739 940 923 190... |
correct output |
---|
296 159 51 231 329 38 47 75 46... |
user output |
---|
296 159 51 231 329 38 47 75 46... |
Test 4
Verdict: ACCEPTED
input |
---|
100 400 545 934 613 647 534 10 587 305... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 5
Verdict: ACCEPTED
input |
---|
100 4000 314 533 236 932 593 139 397 73... |
correct output |
---|
3230 1223 242 3511 2586 1530 1... |
user output |
---|
3230 1223 3226 3511 2586 1957 ... |
Test 6
Verdict: ACCEPTED
input |
---|
100 4000 498 47 243 573 606 538 182 622... |
correct output |
---|
505 1476 2870 3282 2624 1889 3... |
user output |
---|
505 1476 2870 3282 2624 1889 3... |
Test 7
Verdict: ACCEPTED
input |
---|
4000 5000 992 110 627 188 444 785 607 12... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 8
Verdict: ACCEPTED
input |
---|
4000 5000 981 602 417 68 723 17 189 349 ... |
correct output |
---|
impossible |
user output |
---|
impossible |
Test 9
Verdict: ACCEPTED
input |
---|
2000 5000 942 801 7 58 865 535 63 925 45... |
correct output |
---|
2654 2673 4524 642 3560 4043 3... |
user output |
---|
2654 2673 4524 642 3560 4043 3... |
Test 10
Verdict: ACCEPTED
input |
---|
2000 5000 346 342 325 791 867 387 167 43... |
correct output |
---|
2155 1691 1107 4196 3676 396 7... |
user output |
---|
2155 1691 1107 4196 3676 396 7... |
Test 11
Verdict: ACCEPTED
input |
---|
2000 5000 379 181 81 244 67 138 311 763 ... |
correct output |
---|
609 2016 34 1828 252 2270 4016... |
user output |
---|
609 2016 34 1828 252 2270 4016... |
Test 12
Verdict: ACCEPTED
input |
---|
2000 5000 699 504 823 38 915 215 167 649... |
correct output |
---|
2127 3976 4307 4103 2537 2779 ... |
user output |
---|
2127 3976 4307 4103 2537 2779 ... |
Test 13
Verdict: ACCEPTED
input |
---|
1000 5000 769 231 535 397 155 434 183 71... |
correct output |
---|
2149 4078 402 3128 1111 190 40... |
user output |
---|
3194 3088 3323 3128 1111 190 4... |
Test 14
Verdict: ACCEPTED
input |
---|
1000 5000 709 604 503 881 60 756 49 428 ... |
correct output |
---|
1871 3716 4183 3032 2328 731 1... |
user output |
---|
1871 3716 4183 3032 2328 731 1... |
Test 15
Verdict: ACCEPTED
input |
---|
500 5000 41 585 417 384 533 606 594 601... |
correct output |
---|
4475 3687 4699 1002 1733 2047 ... |
user output |
---|
4475 3687 4699 1002 1733 661 2... |
Test 16
Verdict: ACCEPTED
input |
---|
500 5000 812 250 707 106 652 202 79 336... |
correct output |
---|
453 2854 3746 2833 2181 4988 2... |
user output |
---|
453 2854 3746 2833 2181 4988 2... |
Test 17
Verdict: ACCEPTED
input |
---|
500 5000 607 412 339 886 191 583 330 80... |
correct output |
---|
4477 2936 2069 2026 4103 1012 ... |
user output |
---|
4477 2936 2069 2026 4103 1012 ... |
Test 18
Verdict: ACCEPTED
input |
---|
5000 5000 2 3 4 5 6 7 8 9 10 11 12 13 14... |
correct output |
---|
4001 4002 4003 4004 4005 4006 ... |
user output |
---|
4001 4002 4003 4004 4005 4006 ... |