QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#716307#8302. Incoming AsteroidsSouthern_DynastyRE 3ms25776kbC++173.0kb2024-11-06 14:55:122024-11-06 14:55:13

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 14:55:13]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:25776kb
  • [2024-11-06 14:55:12]
  • 提交

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<cur;++i) node[u].now[i]++; 
					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: 3ms
memory: 25776kb

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
...

result: