QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#716364 | #8302. Incoming Asteroids | Southern_Dynasty | RE | 6ms | 26264kb | C++17 | 3.2kb | 2024-11-06 15:01:52 | 2024-11-06 15:01:57 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
#define fst first
#define scd second
#define SZ(s) ((int)s.size())
#define all(s) s.begin(),s.end()
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N=2e5+5;
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,int> pii;
template<class T,class I> inline bool chkmax(T &a,I b){return b>a?a=b,1:0;}
template<class T,class I> inline bool chkmin(T &a,I b){return b<a?a=b,1:0;}
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
x=0;bool sgn=0;static char ch=gt();
while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
if(sgn) x=-x;
}
template<class T,class ...I> inline void read(T &x,I &...x1){
read(x);
read(x1...);
}
template<class T> inline void print(T x){
static char stk[70];short top=0;
if(x<0) pt('-');
do{stk[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top) pt(stk[top--]);
}
template<class T> inline void printsp(T x){
print(x);
putchar(' ');
}
template<class T> inline void println(T x){
print(x);
putchar('\n');
}
int n,m,tag[N],lst;// 减了多少.
set<pii> st[N];
struct Node{
int lim,k;
vector<int> vec,now;
inline void input(){
read(lim);
lim^=lst;
read(k);
k^=lst;
vec.resize(k);
for(int &v:vec) read(v),v^=lst;
}
inline int calc(){
int ans=0;
for(int i=0;i<k;++i) ans+=now[i]-tag[vec[i]];
return ans;
}
}node[N];
signed main(){
read(n,m);
int tot=0;
for(int opt,x,y;m;--m){
read(opt);
if(opt==1){
node[++tot].input();
for(int i=0;i<node[tot].k;++i){
node[tot].now.eb(node[tot].lim/node[tot].k);
}
for(int i=0;i<node[tot].lim%node[tot].k;++i) node[tot].now[i]++;
for(int i=0;i<node[tot].k;++i){
int id=node[tot].vec[i];
node[tot].now[i]+=tag[id];
st[id].insert(pii(node[tot].now[i],tot));
}
}else{
read(x,y);
x^=lst,y^=lst;
tag[x]+=y;
vector<int> ans;
while(SZ(st[x])&&st[x].begin()->fst-tag[x]<=0){
int u=st[x].begin()->scd,cur=node[u].calc();
if(cur<=0){
ans.eb(u);
for(int i=0;i<node[u].k;++i){
int id=node[u].vec[i];
st[id].erase(pii(node[u].now[i],u));
}
}else{
for(int i=0;i<node[u].k;++i){
int id=node[u].vec[i];
st[id].erase(pii(node[u].now[i],u));
}
for(int i=0;i<node[u].k;++i) node[u].now[i]=cur/node[u].k;
cur%=node[u].k;
for(int i=0;i<node[u].k&&cur;++i){
if(node[u].vec[i]==x){
node[u].now[i]++;
cur--;
break;
}
}
for(int i=0;i<node[u].k&&cur;++i){
if(node[u].vec[i]!=x){
node[u].now[i]++;
cur--;
}
}
for(int i=0;i<node[u].k;++i){
int id=node[u].vec[i];
node[u].now[i]+=tag[id];
st[id].insert(pii(node[u].now[i],u));
}
}
}
sort(all(ans));
lst=SZ(ans);
print(lst);
for(int v:ans) pt(' '),print(v);
printf("\n");
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 26264kb
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: -100
Runtime Error
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 ...