QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #619284 | #8302. Incoming Asteroids | DarksideCoder | AC ✓ | 1055ms | 66188kb | C++14 | 2.2kb | 2024-10-07 13:44:52 | 2024-10-07 13:44:53 |
Judging History
answer
#include<bits/stdc++.h>
//#define Debug
using std::vector;
using std::pair;
#define int long long
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
template<typename T>
void Clear(T&x){T y;x.swap(y);}
template<typename... Args>
void Clear(Args&... args){
(Clear(args), ...);//必须加括号
}
std::default_random_engine E(std::chrono::steady_clock().now().time_since_epoch().count());
const int MaxN=410000;
int ind,n,m,Val[MaxN],Le[MaxN],Po[MaxN][4],last;
std::set<pair<ll,ll>>S[MaxN];
int Py[MaxN];
vector<int>Ans,Tmp;
int Pre[MaxN][4],Res[MaxN][4];
signed main(){
#ifdef LOCAL
freopen("In.txt","r",stdin);
freopen("Out.txt","w",stdout);
#endif
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
int opt;
scanf("%lld",&opt);
if(opt==1){
int id=++ind;
scanf("%lld",&Val[id]);Val[id]^=last;
scanf("%lld",&Le[id]);
for(int j=1;j<=Le[id];j++)
scanf("%lld",&Po[id][j]),Po[id][j]^=last;
for(int j=1;j<=Le[id];j++){
int kp=Val[id]/Le[id];
Res[id][j]=Py[Po[id][j]];
if(j==1)S[Po[id][j]].insert({Pre[id][j]=kp+Val[id]%Le[id]+Py[Po[id][j]],id});
else S[Po[id][j]].insert({Pre[id][j]=kp+Py[Po[id][j]],id});
}
}
else{
int po,val;
scanf("%lld%lld",&po,&val);
po^=last,val^=last;
Py[po]+=val;
Clear(Ans);
Clear(Tmp);
for(auto it=S[po].begin();it!=S[po].end();){
auto k=*it;
if(k.fi>Py[po])break;
it=S[po].erase(it);
int id=k.se;
for(int j=1;j<=Le[id];j++){
Val[id]-=Py[Po[id][j]]-Res[id][j];
if(Po[id][j]==po){
continue;
}
S[Po[id][j]].erase({Pre[id][j],id});
}
if(Val[id]<=0)Ans.push_back(id);
else Tmp.push_back(id);
}
for(auto id:Tmp){
for(int j=1;j<=Le[id];j++){
int kp=Val[id]/Le[id];
Res[id][j]=Py[Po[id][j]];
if(j==1)S[Po[id][j]].insert({Pre[id][j]=kp+Val[id]%Le[id]+Py[Po[id][j]],id});
else S[Po[id][j]].insert({Pre[id][j]=kp+Py[Po[id][j]],id});
}
}
printf("%lld",last=Ans.size());
std::sort(Ans.begin(),Ans.end());
for(auto id:Ans)
printf(" %lld",id);
puts("");
}
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32472kb
input:
3 5 1 5 3 1 2 3 2 2 1 1 2 2 1 2 2 3 1 2 1 3
output:
0 0 2 1 2
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 118ms
memory: 59660kb
input:
200000 200000 1 421386 1 122023 2 127573 97972 1 489180 1 197930 2 82505 59100 1 502097 3 91617 14193 139642 2 132931 74031 1 404862 1 36227 2 152826 8462 1 750072 2 51616 75416 2 1547 11479 1 255849 2 70036 41620 2 126414 17120 1 626334 3 97273 190595 174083 2 148803 132 1 407236 2 83898 5103 2 169...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #3:
score: 0
Accepted
time: 98ms
memory: 60132kb
input:
200000 200000 1 312309 2 171927 138033 2 68663 9986 1 409422 3 107618 121948 134622 2 10082 2963 1 555050 1 90783 2 72655 3281 1 933143 3 156038 38059 61251 2 123654 4789 1 491632 2 22976 168618 2 156647 7902 1 389305 3 132923 162027 1538 2 123738 4011 1 362971 3 94150 50751 80442 2 52203 8937 1 205...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #4:
score: 0
Accepted
time: 103ms
memory: 54920kb
input:
200000 200000 1 142543 1 115092 2 171364 77800 1 175929 3 183076 20412 144389 2 44523 136842 1 342332 3 155151 4240 89238 2 111001 39417 1 133140 2 69162 186231 2 170481 10806 1 680994 2 138407 7106 2 170161 198340 1 772506 1 109120 2 24352 199102 1 901774 2 114997 161429 2 74138 125234 1 757250 1 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #5:
score: 0
Accepted
time: 191ms
memory: 59760kb
input:
20000 200000 1 678769 3 4395 16744 14145 2 8935 15738 1 432048 3 9768 6009 16504 2 12630 12968 1 397741 3 223 1836 378 2 257 18108 1 850814 3 4564 13454 7781 2 2124 13159 1 252004 3 15683 16496 18755 2 5458 25974 1 433880 3 5518 9833 9661 2 1925 405 1 892145 3 15731 16871 19282 2 17132 17115 1 81156...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #6:
score: 0
Accepted
time: 305ms
memory: 54276kb
input:
4000 200000 1 302161 3 2309 1618 194 2 3316 19207 1 878861 3 2986 2907 146 2 3099 26347 1 932183 3 648 3750 1939 2 29 23023 1 327262 3 2959 548 986 2 3356 22562 1 542484 3 490 465 3590 2 3121 1669 1 246973 3 1328 3985 605 2 75 1839 1 392188 3 658 2867 1928 2 800 29554 1 315643 3 157 2426 331 2 600 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #7:
score: 0
Accepted
time: 248ms
memory: 45072kb
input:
200 200000 1 44130 3 22 167 30 2 107 8878 1 391579 3 107 68 58 2 179 166 1 797413 3 85 145 186 2 128 18222 1 588792 3 78 104 10 2 168 5761 1 720090 3 33 198 62 2 26 16475 1 342624 3 49 94 153 2 34 4317 1 410548 3 197 166 55 2 124 8507 1 985428 3 1 158 126 2 174 14078 1 32984 3 112 126 55 2 59 15762 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 105 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #8:
score: 0
Accepted
time: 215ms
memory: 43108kb
input:
17 200000 1 194788 3 1 9 6 2 7 18685 1 668957 3 8 12 16 2 5 25666 1 526243 3 13 7 5 2 8 14143 1 49467 3 8 1 17 2 3 25053 1 776279 3 7 11 6 2 5 23689 1 652474 3 4 11 16 2 2 16447 1 104480 3 5 3 14 2 9 23069 1 699675 3 2 15 14 2 3 18743 1 888214 3 17 2 4 2 8 24619 1 626162 3 14 17 3 2 12 20407 1 65049...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 7 0 1 38 0 0 0 0 1 20 0 0 1 28 0 0 0 0 0 0 0 1 23 1 21 0 1 40 0 1 32 0 0 0 0 0 0 0 0 0 0 0 2 1 62 0 0 0 0 1 27 1 42 0 3 53 63 81 1 57 0 1 45 1 34 0 0 0 0 0 0 0 1 60 0 0 0 0 1 52 0 2 15 89 0 2 54 94 0 1 70 0 0 1 61 0 0 0 ...
result:
ok 100000 lines
Test #9:
score: 0
Accepted
time: 441ms
memory: 64316kb
input:
200000 200000 1 595793 3 1 123431 117674 2 1 5 1 488610 3 1 177503 120691 2 1 5 1 821006 3 1 89129 8171 2 1 3 1 202425 3 1 98222 39855 2 1 1 1 173441 3 1 47510 50873 2 1 1 1 43994 3 1 150434 88334 2 1 3 1 336575 3 1 100731 143443 2 139351 30393 1 867 3 1 155149 2891 2 1 3 1 22448 3 1 193793 152032 2...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #10:
score: 0
Accepted
time: 303ms
memory: 65636kb
input:
200000 200000 1 228748 3 2 98560 10598 2 1 2 1 808541 3 2 34857 97574 2 1 5 1 426853 3 1 76426 192070 2 2 4 1 747544 3 1 105439 24822 2 2 5 1 931575 3 2 162805 154073 2 2 3 1 208881 3 1 185615 2914 2 2 5 1 670938 3 2 60855 116483 2 1 5 1 73426 3 2 24690 9141 2 2 5 1 260124 3 2 97655 111375 2 1 2 1 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #11:
score: 0
Accepted
time: 735ms
memory: 54124kb
input:
200000 200000 1 210052 3 1 36549 161634 2 1 10 1 915616 3 3 184683 70284 2 162377 99788 1 772478 3 3 105049 182326 2 1 20 1 379608 3 1 39390 19098 2 99945 52401 1 830086 3 2 174499 190942 2 3 16 1 363236 3 3 115751 9885 2 2 21 1 943439 3 2 80258 46001 2 1 36 1 875219 3 3 143998 53331 2 38341 2315 1 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #12:
score: 0
Accepted
time: 1055ms
memory: 64028kb
input:
200000 200000 1 2 3 1 143865 120099 1 4 3 1 190911 25916 1 6 3 1 178053 186643 1 8 3 1 141036 104525 1 10 3 1 80225 74496 1 12 3 1 105364 55824 1 14 3 1 115552 32637 1 16 3 1 112278 121633 1 18 3 1 145162 78825 1 20 3 1 20698 115991 1 22 3 1 127458 88470 1 24 3 1 66991 13619 1 26 3 1 124342 175360 1...
output:
1 1 0 1 2 1 3 0 1 4 1 5 0 0 1 6 1 7 1 8 1 9 1 10 0 1 11 0 1 12 0 1 177 1 13 1 14 1 15 1 20357 1 16 1 17 0 1 18 1 19 1 20 1 21 0 1 22 1 23 1 24 0 1 25 1 26 1 27 1 28 0 1 29 0 0 1 30 0 1 31 1 32 1 33 1 34 1 35 1 36 0 1 37 0 0 1 38 1 39 0 0 1 40 0 1 41 0 0 1 42 0 1 43 1 44 0 0 1 45 1 46 1 47 1 48 0 0 1...
result:
ok 100000 lines
Test #13:
score: 0
Accepted
time: 593ms
memory: 66188kb
input:
200000 200000 1 2 3 1 101192 15219 1 4 3 1 57934 110363 1 6 3 1 166877 20608 1 8 3 1 140315 92121 1 10 3 1 154860 172141 1 12 3 2 146060 34724 1 14 3 2 152086 127672 1 16 3 2 121076 179495 1 18 3 1 176976 8288 1 20 3 2 28013 56218 1 22 3 1 58459 127899 1 24 3 1 186216 156690 1 26 3 2 72780 26800 1 2...
output:
0 0 0 0 0 0 0 1 1 0 0 0 1 31707 0 1 2 1 6 0 1 3 0 0 1 7 1 8 1 3479 1 4 0 1 5 1 10 0 0 0 0 0 0 0 0 0 0 0 1 9 0 0 1 11 0 0 1 13 0 0 1 14 1 15 1 12 0 0 0 0 0 1 16 1 17 0 0 0 0 0 0 0 0 0 0 0 1 18 1 19 1 21 1 20 0 0 0 1 22 0 0 0 0 0 0 0 0 1 23 1 24 0 0 1 25 0 1 27 0 1 26 0 1 28 0 0 0 0 0 1 30 1 31 0 1 29...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 421ms
memory: 64164kb
input:
200000 200000 1 2 3 2 55477 107917 1 4 3 3 19358 69971 1 6 3 3 4845 25684 1 8 3 3 87244 180552 1 10 3 1 26548 17274 1 12 3 2 139729 23824 1 14 3 2 188857 68666 1 16 3 3 35589 45253 1 18 3 1 90845 23176 1 20 3 1 168245 46115 1 22 3 3 80442 114240 1 24 3 3 111250 13936 1 26 3 3 174868 145017 1 28 3 3 ...
output:
1 1 0 0 0 0 0 0 0 1 2 0 0 1 3 0 0 1 4 0 0 0 0 0 1 5 0 0 0 0 0 0 0 1 9 0 1 10 0 1 8 0 0 0 0 0 0 0 1 6 1 11 0 1 12 0 0 0 1 13 0 1 7 1 14 0 0 0 0 0 0 1 19 0 0 0 0 0 0 0 0 1 22 0 0 0 0 0 0 0 1 16 0 0 0 1 17 0 0 0 0 1 15 0 0 0 0 0 0 0 1 27 0 1 18 0 1 6695 1 9734 0 0 0 0 0 1 32686 0 0 1 29 0 0 0 0 0 1 20 ...
result:
ok 100000 lines
Extra Test:
score: 0
Extra Test Passed