QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #393023 | #527. Particles | mraron | 65 | 907ms | 11936kb | C++14 | 2.0kb | 2024-04-18 03:35:42 | 2024-04-18 03:35:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct particle {
ll start_t, start_pos;
ll dir;
ll v;
int ind;
double pos_at(double T) const {
return (double)start_pos+dir*(T-start_t)*v;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n,l,k;
cin>>n>>l>>k;
vector<particle> x(n),y(n);
for(int i=0;i<n;++i) {
cin>>x[i].start_t>>x[i].v;
x[i].dir=1;
x[i].start_pos=0;
x[i].ind=i;
}
for(int i=0;i<n;++i) {
cin>>y[i].start_t>>y[i].v;
y[i].dir=-1;
y[i].start_pos=l;
y[i].ind=i;
}
auto get_range=[&](double T, vector<particle>& lst) -> pair<int, int> {
pair<int, int> res={0,0};
for(int i=1;i<(int)lst.size();++i) {
if(lst[res.first].pos_at(T)>lst[i].pos_at(T)) res.first=i;
if(lst[res.second].pos_at(T)<lst[i].pos_at(T)) res.second=i;
}
return res;
};
vector<particle> lstX, lstY;
for(int i=0;i<n;++i) lstX.push_back(x[i]);
for(int i=0;i<n;++i) lstY.push_back(y[i]);
for(int i=0;i<k;++i) {
double L=0.0, R=1e9;
for(int j=0;j<(int)lstX.size();++j) {
R=min(R, lstX[j].start_t+double(l)/lstX[j].v);
R=min(R, lstY[j].start_t+double(l)/lstY[j].v);
}
int XX, YY;
int its=0;
while(its++<40) {
double mid=(L+R)/2;
pair<int,int> xRan=get_range(mid, lstX);
pair<int,int> yRan=get_range(mid, lstY);
XX=xRan.second;
YY=yRan.first;
if(lstX[xRan.second].pos_at(mid)<lstY[yRan.first].pos_at(mid)) L=mid;
else R=mid;
}
cout<<lstX[XX].ind+1<<" "<<lstY[YY].ind+1<<"\n";
swap(lstX[XX], lstX[(int)lstX.size()-1]);lstX.pop_back();
swap(lstY[YY], lstY[(int)lstY.size()-1]);lstY.pop_back();
}
}
詳細信息
Test #1:
score: 5
Accepted
time: 1ms
memory: 3620kb
input:
10 1000 4 0 58 4 80 5 69 9 681 18 96 20 244 29 78 30 876 31 19 37 255 0 491 4 100 5 299 9 58 18 868 20 6 29 325 30 84 31 922 37 6
output:
1 1 2 3 4 2 3 4
result:
ok 4 lines
Test #2:
score: 5
Accepted
time: 2ms
memory: 3636kb
input:
100 10000 70 0 525 9 8678 16 189 22 850 26 708 30 2910 36 610 44 3339 49 6 57 4897 60 422 66 3753 71 512 80 9195 86 681 96 4961 101 208 110 9345 119 509 120 5531 125 793 131 5149 141 791 147 6621 149 768 151 5727 154 790 160 8441 167 43 172 715 181 349 183 603 189 481 195 1092 205 680 211 6873 218 9...
output:
1 1 2 2 3 3 4 5 6 4 5 6 8 7 7 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 20 19 19 21 22 20 21 22 24 23 23 24 26 25 25 27 28 26 27 28 29 29 30 30 32 31 31 32 33 33 34 34 35 35 36 36 37 37 38 39 40 38 39 41 42 40 41 42 43 43 44 44 45 45 46 47 48 46 47 48 49 49 50 50 51 51 52 52 53 53 ...
result:
ok 70 lines
Test #3:
score: 5
Accepted
time: 0ms
memory: 3608kb
input:
210 15000 45 0 1211 3 3286 12 834 22 12572 32 415 38 1263 42 593 51 5190 59 1198 62 13504 66 238 69 7009 79 118 86 1929 95 1199 100 6846 108 1157 109 2671 116 1118 126 13053 131 1306 139 1221 147 753 150 7071 160 378 163 1845 173 200 183 877 190 250 195 6701 197 595 207 1957 214 655 217 14649 219 47...
output:
1 1 2 2 3 3 4 4 5 5 6 7 7 6 8 8 9 9 10 10 12 11 11 13 14 12 13 15 15 14 16 16 18 17 17 19 20 18 19 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 29 30 31 32 32 31 33 34 30 29 35 33 34 36 28 35 37 38 39 37 38 40 40 41 41 42 36 39 43 44 42 43 44 45 45
result:
ok 45 lines
Test #4:
score: 5
Accepted
time: 9ms
memory: 3724kb
input:
460 100000 85 0 6019 6 31917 9 2718 11 33284 20 7288 28 87899 36 1911 37 66667 47 9132 50 76339 58 70 63 25931 70 4259 77 1924 86 2586 93 53721 102 7562 108 58815 114 2327 122 95239 130 1275 137 67506 141 4802 150 65865 156 1677 164 38724 166 472 167 35589 168 7444 175 99881 181 3240 188 53703 195 2...
output:
2 1 1 3 4 2 3 4 5 5 6 6 8 7 7 9 10 10 9 8 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 28 27 29 29 30 28 32 30 31 31 27 33 34 32 33 34 36 35 35 37 38 39 40 38 39 41 41 36 42 40 43 43 44 42 45 45 46 44 48 47 47 49 50 50 49 51 52 48 51 46 53 53 54 52 ...
result:
ok 85 lines
Test #5:
score: 5
Accepted
time: 15ms
memory: 3728kb
input:
690 200000 90 0 4 10 170196 20 37 24 6457 27 174 35 51169 37 182 39 102355 40 80 44 196417 46 83 51 174154 53 178 62 196525 72 90 77 179539 87 18 97 145321 102 118 103 112849 113 126 117 193295 120 25 123 39978 133 123 134 117901 144 107 150 102259 159 178 168 66645 169 14 176 75806 183 169 186 1396...
output:
2 1 4 3 6 5 8 7 10 9 12 11 5 13 14 2 16 15 18 17 20 19 22 12 24 23 26 25 28 27 7 29 30 21 32 31 34 33 13 35 36 8 38 4 40 39 42 41 44 43 46 45 19 47 48 37 50 49 52 51 54 53 56 55 58 57 60 59 62 61 64 24 29 65 66 10 68 63 33 69 70 67 72 16 74 71 21 75 76 44 25 77 78 28 80 79 82 83 84 81 86 85 88 89 90...
result:
ok 90 lines
Test #6:
score: 5
Accepted
time: 20ms
memory: 3860kb
input:
1000 3000000 100 0 783 1 1448348 10 348 12 1750907 20 378 24 2102523 30 97 39 2402616 46 179 53 1270831 54 90 60 1779163 63 278 70 1359031 80 529 83 2544605 86 355 87 2552759 92 469 93 168851 94 871 96 2102006 106 583 113 2760719 117 77 120 1498356 129 800 137 2411313 139 936 140 1131747 142 887 149...
output:
2 1 4 3 1 5 6 2 3 7 8 4 5 9 10 11 12 8 7 13 14 6 9 15 16 10 18 17 22 21 20 19 15 23 24 12 26 25 28 27 30 29 21 31 32 18 19 33 34 20 36 37 38 35 23 39 40 36 27 41 42 32 44 43 46 45 29 47 48 38 31 49 50 40 33 51 52 30 54 53 35 55 56 57 58 59 60 61 62 48 64 63 47 65 66 42 68 67 45 69 70 44 41 71 72 73 ...
result:
ok 100 lines
Test #7:
score: 5
Accepted
time: 187ms
memory: 5288kb
input:
9500 1000000000 82 0 22 2 28 7 689 12 55 14 23 17 77 25 306 34 81 38 946 46 57 50 960 51 53 54 647 62 7 67 991 77 97 81 183 84 85 94 328 101 23 102 595 111 15 113 778 119 9 121 231 123 45 126 173 129 45 131 456 134 72 141 479 143 37 148 57 149 91 154 855 156 57 164 868 171 89 181 318 190 93 199 203 ...
output:
15 9481 117 9483 115 9485 221 9487 279 9489 125 9491 203 9493 11 9495 181 9497 133 9499 763 431 757 487 1161 839 491 981 1779 1341 1787 1147 1711 1801 2051 315 831 107 2137 1633 1225 2023 1861 2159 717 2193 2355 1847 1119 889 1739 717 2495 237 567 87 2065 1761 1641 3103 2997 1095 1811 2683 2939 725 ...
result:
ok 82 lines
Test #8:
score: 5
Accepted
time: 267ms
memory: 5572kb
input:
13200 1000000000 84 0 827 9 81 19 994 28 39 35 466 36 8 42 784 48 78 57 290 58 79 68 555 73 61 74 928 75 89 82 431 84 69 90 564 97 26 105 987 114 55 121 482 123 93 132 342 140 73 141 733 147 26 154 407 159 19 163 386 164 65 168 877 169 13 177 36 182 32 192 366 196 81 202 432 205 33 213 574 221 87 22...
output:
3 13181 19 13183 105 13185 241 13187 211 13189 351 13191 201 13193 639 13195 557 13197 147 13199 1453 347 1439 1061 1301 543 1821 563 1979 17 1371 1107 1787 675 1703 1389 2427 309 581 1239 999 1921 631 915 1403 315 489 1069 2931 2211 1019 1147 1975 629 2093 2487 1599 1221 2761 945 3327 521 867 345 2...
result:
ok 84 lines
Test #9:
score: 5
Accepted
time: 369ms
memory: 7272kb
input:
18000 1000000000 86 0 372 1 97 9 397 19 21 27 766 35 81 40 661 45 13 54 136 59 89 64 364 74 86 79 565 82 88 92 630 94 5 96 138 105 21 113 300 115 23 120 174 126 49 136 41 139 77 141 712 143 31 152 401 162 41 166 417 170 27 177 313 183 69 184 172 192 39 201 698 207 38 213 808 219 57 220 978 227 4 229...
output:
93 17961 215 17963 51 17965 281 17967 39 17969 199 17971 447 17973 359 17975 65 17977 479 17979 115 17981 565 17983 343 17985 797 17987 203 17989 557 17991 279 17993 729 17995 989 17997 579 17999 1053 247 1507 19 1645 703 1119 1119 2257 671 1413 1009 1659 263 1381 103 2679 225 1921 1245 893 1255 773...
result:
ok 86 lines
Test #10:
score: 5
Accepted
time: 517ms
memory: 8144kb
input:
25000 990000000 86 0 820 3 25 13 71 15 5 16 271 19 71 25 915 29 32 36 196 40 1 44 320 53 91 54 711 57 1 66 794 73 55 74 592 84 5 88 930 93 9 94 374 95 53 105 975 109 41 117 747 121 46 129 694 134 61 143 198 153 7 154 741 158 96 168 932 169 53 172 774 173 97 177 565 178 37 184 216 193 81 199 355 200 ...
output:
73 24961 63 24963 241 24965 193 24967 43 24969 23 24971 591 24973 317 24975 737 24977 157 24979 115 24981 787 24983 941 24985 379 24987 179 24989 749 24991 235 24993 805 24995 1155 24997 823 24999 1405 259 1629 709 1365 559 1549 157 2201 275 2463 503 1593 699 1039 749 3055 1175 2997 593 2033 35 2681...
result:
ok 86 lines
Test #11:
score: 5
Accepted
time: 684ms
memory: 8548kb
input:
30000 990000000 90 0 808 2 77 12 386 13 21 22 500 31 87 40 517 48 51 53 423 54 35 63 678 70 3 72 278 78 45 86 660 90 19 100 50 109 31 110 897 113 59 120 846 128 9 137 986 147 10 148 977 158 33 167 739 176 88 183 172 184 85 193 644 194 29 200 913 204 67 206 476 212 35 215 9 225 66 228 310 233 65 239 ...
output:
347 29961 23 29963 75 29965 413 29967 77 29969 25 29971 569 29973 329 29975 315 29977 451 29979 463 29981 487 29983 903 29985 249 29987 215 29989 245 29991 439 29993 231 29995 1093 29997 713 29999 1311 191 2117 219 2541 469 1213 1 2003 1323 1509 11 1719 655 2183 1283 645 1357 2981 1579 2297 1277 190...
result:
ok 90 lines
Test #12:
score: 5
Accepted
time: 749ms
memory: 10988kb
input:
34000 1000000000 92 0 651 7 17 12 302 22 1 25 695 29 81 37 562 40 59 49 355 53 100 62 788 72 19 81 157 82 11 90 581 97 77 100 587 107 78 111 969 113 61 121 795 128 17 130 765 139 2 143 982 147 15 153 793 157 11 167 441 174 41 175 513 183 13 185 487 192 41 197 150 203 59 205 664 209 91 215 40 225 53 ...
output:
165 16961 25 16963 203 16965 323 16967 275 16969 331 16971 301 16973 19 16975 585 16977 363 16979 81 16981 515 16983 87 16985 217 16987 567 16989 791 16991 815 16993 313 16995 597 16997 615 16999 475 17001 1049 17003 699 17005 485 17007 213 17009 871 17011 965 17013 229 17015 345 17017 41 17019 329 ...
result:
ok 92 lines
Test #13:
score: 5
Accepted
time: 907ms
memory: 11936kb
input:
40000 1000000000 95 0 461 4 97 10 91 14 25 22 782 29 51 39 801 41 41 44 352 46 25 55 853 57 61 62 496 66 97 74 807 79 45 82 521 83 43 84 704 88 17 89 842 97 41 101 172 106 13 114 680 115 97 120 949 125 61 134 383 135 57 139 762 149 8 153 686 161 41 171 896 180 59 188 201 193 75 200 355 205 1 212 956...
output:
247 26643 389 26645 369 26647 479 26649 295 26651 631 26653 497 26655 791 26657 103 26659 301 26661 41 26663 267 26665 681 26667 27 26669 1095 26671 1171 26673 1001 26675 1333 26677 937 26679 1549 26681 1423 26683 527 26685 833 26687 339 26689 1675 17 1747 801 1947 323 2303 655 1969 539 1997 177 181...
result:
ok 95 lines
Test #14:
score: 0
Time Limit Exceeded
input:
43000 1000000000 100 0 385 9 97 17 243 19 87 28 461 31 66 37 49 45 16 46 908 50 5 52 760 61 41 71 795 79 93 85 447 92 83 101 197 107 73 109 522 113 93 117 667 125 58 135 931 142 57 143 864 153 51 160 246 167 16 170 782 174 67 176 58 183 57 191 274 200 47 208 402 218 77 225 178 229 17 232 953 237 21 ...
output:
211 28643 225 28645 195 28647 279 28649 447 28651 715 28653 91 28655 969 28657 663 28659 139 28661 1149 28663 1227 28665 39 28667 895 28669 1367 28671 457 28673 1195 28675 1191 28677 1053 28679 1241 28681 173 28683 703 28685 673 28687 833 28689 1695 531 1675 431 2037 697 1497 1027 1493 1151 2117 27 ...
result:
Test #15:
score: 0
Time Limit Exceeded
input:
46000 1000000000 100 0 12 9 29 16 512 26 3 34 831 35 80 37 626 43 89 46 229 52 74 55 894 56 19 57 152 58 49 67 304 72 85 77 806 78 33 87 49 96 49 103 332 113 73 122 880 126 21 131 246 138 13 147 504 148 37 157 85 160 27 161 461 169 61 172 775 176 55 180 486 188 52 198 120 207 39 216 942 222 65 230 2...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
50000 1000000000 100 0 653 4 1 5 355 12 85 19 651 20 40 24 844 27 31 29 273 31 43 38 36 40 36 47 47 49 93 52 118 58 1 60 552 69 21 77 669 85 85 92 884 102 29 103 21 106 21 111 539 117 81 124 953 130 61 134 233 136 93 141 835 145 21 154 886 155 17 157 914 166 17 169 209 177 81 179 852 182 21 183 953 ...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
50000 1000000000 100 0 964 8 35 10 852 12 5 14 814 21 41 25 715 30 21 36 697 45 93 54 46 64 23 69 655 78 17 81 710 91 3 92 331 96 37 105 610 109 40 110 492 119 59 125 28 131 12 134 544 136 26 138 649 144 15 147 168 154 77 155 1 159 81 165 716 167 49 171 520 180 35 182 210 192 9 200 944 202 77 206 47...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
50000 1000000000 100 0 179 7 61 9 687 18 55 22 674 25 43 31 692 40 71 46 367 49 37 59 90 68 11 72 521 77 41 79 321 88 26 93 853 98 13 104 763 109 81 114 110 115 1 118 449 121 25 125 188 127 81 132 719 133 63 141 880 151 26 158 481 164 1 165 359 171 43 172 153 174 50 175 639 180 92 190 842 191 17 192...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
50000 1000000000 100 0 260 1 78 3 415 7 51 9 360 16 45 19 48 29 16 36 506 42 99 43 497 52 49 53 830 59 85 65 805 68 90 76 694 79 13 84 270 91 75 99 857 109 76 111 800 113 1 123 435 126 81 133 548 135 93 145 572 146 6 156 497 162 81 169 830 171 5 180 208 186 98 189 761 197 1 204 467 211 57 218 687 22...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
50000 1000000000 100 0 670 2 137 4 627 6 401 8 151 10 701 12 349 14 556 16 532 18 574 20 794 22 531 24 241 26 905 28 641 30 241 32 373 34 957 36 501 38 777 40 8 42 825 44 450 46 561 48 941 50 146 52 561 54 321 56 649 58 691 60 787 62 233 64 5 66 1 68 687 70 805 72 691 74 613 76 147 78 705 80 313 82 ...