QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#371601 | #8302. Incoming Asteroids | ucup-team052# | WA | 1ms | 3880kb | C++23 | 2.1kb | 2024-03-30 14:20:28 | 2024-03-30 14:20:29 |
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();
printf("%lld ",_lst);
for(int i=0;i<_lst;i++) printf("%lld ",ans[i]);
printf("\n");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3880kb
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:
wrong answer 1st lines differ - expected: '0', found: '0 '