QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#371606 | #8302. Incoming Asteroids | ucup-team052# | WA | 140ms | 37052kb | C++23 | 2.1kb | 2024-03-30 14:22:51 | 2024-03-30 14:24:26 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
using LL=long long;
const int inf=0x3f3f3f3f;
#define int long long
#define N 200005
const int MAGIC=1000;
int read()
{
int x; scanf("%lld",&x);
return x;
}
int n,Q,m;
int sz[N],q[N][3],lst[N][3],start[N][3],sum[N],ned[N],ok[N];
vector<int> presum[N],all[N],ready[N];
int lstpos[N];
void wait(int id)
{
for(int i=0;i<sz[id];i++) all[q[id][i]].push_back(id);
if(ned[id]<=sz[id]*MAGIC)
{
for(int i=0;i<sz[id];i++) ready[q[id][i]].push_back(id);
}
}
int getsiz(int id)
{
int sum=0;
for(int i=0;i<sz[id];i++)
{
int u=q[id][i],st=start[id][i];
sum+=presum[u].back()-presum[u][st];
}
return sum;
}
vector<int> ans;
signed main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
cin>>n>>Q;
int _lst=0;
for(int i=1;i<=n;i++) presum[i].push_back(0);
while(Q--)
{
int op=read();
if(op==1)
{
m++;
ned[m]=read()^_lst,sz[m]=read();
for(int i=0;i<sz[m];i++)
{
q[m][i]=read()^_lst;
start[m][i]=presum[q[m][i]].size()-1;
}
wait(m);
}
else
{
int x=read()^_lst,y=read()^_lst;
presum[x].push_back(presum[x].back()+y);
ans.clear();
if(presum[x].back()-presum[x][lstpos[x]]<MAGIC)
{
vector<int> nw;
for(int j:ready[x])
{
if(ok[j]==1) continue;
if(getsiz(j)>=ned[j]) ans.push_back(j),ok[j]=1;
else nw.push_back(j);
}
swap(ready[x],nw);
}
else
{
vector<int> nw;
for(int j:all[x])
{
if(ok[j]==1) continue;
int siz=getsiz(j);
if(siz>=ned[j]) ans.push_back(j),ok[j]=1;
else
{
nw.push_back(j);
if(ok[j]!=2&&ned[j]-siz<=sz[j]*MAGIC)
{
ok[j]=2;
for(int i=0;i<sz[j];i++) ready[q[j][i]].push_back(j);
}
}
}
swap(all[x],nw);
lstpos[x]=presum[x].size()-1;
}
_lst=ans.size();
if(_lst==0) printf("0\n");
else
{
printf("%lld ",_lst);
for(int i=0;i<_lst;i++) printf("%lld%c",ans[i]," \n"[i==_lst-1]);
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3804kb
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: 113ms
memory: 36092kb
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: 125ms
memory: 37052kb
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: 134ms
memory: 35524kb
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: 123ms
memory: 18100kb
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: 140ms
memory: 14700kb
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: -100
Wrong Answer
time: 101ms
memory: 11932kb
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:
wrong answer 89097th lines differ - expected: '2 85906 88530', found: '2 88530 85906'