QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698499#9519. Build a ComputerAnotherDayofSun#AC ✓4ms15688kbC++143.6kb2024-11-01 19:59:252024-11-01 19:59:26

Judging History

This is the latest submission verdict.

  • [2024-11-01 19:59:26]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 15688kb
  • [2024-11-01 19:59:25]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mkp make_pair
#define vi vector<int>
#define SZ(x) ((int)x.size())
#define pii pair<int,int>
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define foR(i,k,j) for(int i=(k);i>=(j);i--)
#define For(i,k,j) for(int i=(k);i<=(j);i++)
#define Foe(i,u) for(int i=lst[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define Fin(s) freopen(s,"r",stdin)
#define Fout(s) freopen(s,"w",stdout)
#define file(s) Fin(s".in"),Fout(s".out")
#define INF ((1<<30)-1)
//#define int long long
const int P=998244353; //
using namespace std;
template<typename T>inline void ckmax(T &a,T b) {(a<b)&&(a=b);}
template<typename T>inline void ckmin(T &a,T b) {(a>b)&&(a=b);}
inline int mul(int a,int b) {return 1ll*a*b%P;}
inline int add(int a,int b) {return a+b>=P?a+b-P:a+b;}
inline int sub(int a,int b) {return a-b>=0?a-b:a-b+P;}
inline void mulmod(int &a,int b) {a=mul(a, b);}
inline void addmod(int &a,int b) {((a+=b)>=P)&&(a-=P);}
inline void submod(int &a,int b) {((a-=b)<0)&&(a+=P);}
inline int ksm(int a,int b) {int ans=1; for(;b;b>>=1) {if(b&1) ans=1ll*ans*a%P;a=1ll*a*a%P;}return ans;}
inline void fprint(const vector<int> &f) {for(int i=0;i<(int)f.size();i++) fprintf(stderr,"%d ",f[i]); fprintf(stderr,"\n");}
inline int inv(int a) {return ksm(a,P-2);}
namespace FastIO {
	const int SIZE=1<<16; char buf[SIZE],obuf[SIZE],str[64]; int bi=SIZE,bn=SIZE,opt;
	int read(char *s) {
		while (bn) {for (;bi<bn&&buf[bi]<=' ';bi++);if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}
		int sn=0;while (bn) {for (;bi<bn&&buf[bi]>' ';bi++) s[sn++]=buf[bi];if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}s[sn]=0;return sn;
	}
	bool read(int& x) {if(x)x=0;int bf=0,n=read(str); if(!n) return 0; int i=0; if (str[i]=='-') bf=1,i=1; for(x=0;i<n;i++) x=x*10+str[i]-'0'; if(bf) x=-x; return 1;}
	void write(int x) {
		if(!x) obuf[opt++]='0'; else {if(x<0) obuf[opt++]='-',x=-x;int sn=0; while(x)str[sn++]=x%10+'0',x/=10;for (int i=sn-1;i>=0;i--) obuf[opt++]=str[i];}
		if (opt>=(SIZE>>1)){fwrite(obuf,1,opt,stdout); opt=0;}
	}
	void write(char x) {obuf[opt++]=x;if (opt>=(SIZE>>1)){fwrite(obuf,1,opt,stdout); opt=0;}}
	void Fflush() {if (opt) fwrite(obuf,1,opt,stdout); opt=0;}
};
inline int read() {int x; FI(x); return x;}
const int MN=5e5+5; 
vi g[MN]; int tot,rt,mx; 
void getans(int l,int r,int L,int R,int dep) {
	// cerr<<k<<' '<<l<<' '<<r<<endl;
	if(L<=l&&r<=R) {
		mx=max(mx,dep); 
		return; 
	}
	int mid=(l+r)>>1;
	if(L<=mid) getans(l,mid,L,R,dep-1);  
	if(mid<R) getans(mid+1,r,L,R,dep-1); 
}
void build(int &k,int l,int r,int L,int R,int dep,int lz,int fr) {
	if(lz||fr==-1) {
		if(l!=r) k=++tot; 
		else k=1; 
	}
	if(lz||fr==-1) fr=k; 
	if(L<=l&&r<=R) {
		if(dep>=1) {
			g[fr].pb(dep); 
			g[fr].pb(-dep); 	
		} 
		return; 
	}
	int mid=(l+r)>>1;
	int lc=0,rc=0;
	if(L<=mid) {
		build(lc,l,mid,L,R,dep-1,lz,fr);
		if(lc) g[fr].pb(-lc);  	
	}
	if(mid<R) build(rc,mid+1,r,L,R,dep-1,1,fr),g[fr].pb(rc); 

}
void works() {
	int L=read(),R=read();  getans(0,(1<<20)-1,L,R,20);
	tot++; For(i,0,mx-2) tot++,g[tot].pb(tot-1),g[tot].pb(1-tot);
	build(rt,0,(1<<20)-1,L,R,20,0,-1);
	printf("%d\n",tot); 
	For(i,1,tot) {
		printf("%d ",SZ(g[i])); 
		for(auto it:g[i]) {
			printf("%d %d ",abs(it),it>0); 
		}
		printf("\n"); 
	}
}
int main(){
	#ifdef wasa855
		freopen("pro.in","r",stdin);
		freopen("pro.out","w",stdout);
	#endif
	int T=1;  
	while(T--) {
		works(); 
	}
	return FastIO::Fflush(),0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 15580kb

input:

5 7

output:

5
0 
1 3 1 
2 4 0 5 1 
1 1 1 
2 1 1 1 0 

result:

ok ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 15512kb

input:

10 27

output:

12
0 
2 1 1 1 0 
2 2 1 2 0 
2 5 1 9 1 
2 6 0 8 1 
1 7 1 
2 1 1 1 0 
2 2 1 2 0 
2 10 0 11 1 
2 3 1 3 0 
1 12 0 
2 2 1 2 0 

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 15572kb

input:

5 13

output:

10
0 
2 1 1 1 0 
2 4 1 7 1 
2 5 0 6 1 
1 1 1 
2 1 1 1 0 
2 8 0 9 1 
2 2 1 2 0 
1 10 0 
2 1 1 1 0 

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 15564kb

input:

1 1000000

output:

62
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
20 1 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1...

result:

ok ok

Test #5:

score: 0
Accepted
time: 0ms
memory: 15572kb

input:

1 1

output:

2
0 
1 1 1 

result:

ok ok

Test #6:

score: 0
Accepted
time: 0ms
memory: 15556kb

input:

7 9

output:

7
0 
2 3 1 5 1 
1 4 1 
1 1 1 
1 6 0 
1 7 0 
2 1 1 1 0 

result:

ok ok

Test #7:

score: 0
Accepted
time: 3ms
memory: 15576kb

input:

3 7

output:

5
0 
2 1 1 1 0 
2 4 1 5 1 
1 1 1 
2 2 1 2 0 

result:

ok ok

Test #8:

score: 0
Accepted
time: 3ms
memory: 15572kb

input:

1 5

output:

5
0 
3 1 1 3 1 4 1 
2 1 1 1 0 
1 5 0 
2 1 1 1 0 

result:

ok ok

Test #9:

score: 0
Accepted
time: 0ms
memory: 15516kb

input:

1 4

output:

5
0 
3 1 1 3 1 4 1 
2 1 1 1 0 
1 5 0 
1 1 0 

result:

ok ok

Test #10:

score: 0
Accepted
time: 0ms
memory: 15508kb

input:

8 9

output:

5
0 
1 3 1 
1 4 0 
1 5 0 
2 1 1 1 0 

result:

ok ok

Test #11:

score: 0
Accepted
time: 3ms
memory: 15504kb

input:

7 51

output:

14
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
4 6 1 8 1 9 1 10 1 
1 7 1 
1 1 1 
2 3 1 3 0 
2 4 1 4 0 
2 11 0 12 1 
2 4 1 4 0 
1 13 0 
1 14 0 
2 2 1 2 0 

result:

ok ok

Test #12:

score: 0
Accepted
time: 3ms
memory: 15604kb

input:

51 79

output:

15
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 6 1 13 1 
1 7 1 
2 8 0 12 1 
2 9 0 11 1 
1 10 1 
1 1 1 
2 2 1 2 0 
2 3 1 3 0 
1 14 0 
1 15 0 
2 4 1 4 0 

result:

ok ok

Test #13:

score: 0
Accepted
time: 0ms
memory: 15568kb

input:

92 99

output:

12
0 
2 1 1 1 0 
1 4 1 
2 5 0 9 1 
1 6 1 
1 7 1 
1 8 1 
2 2 1 2 0 
1 10 0 
1 11 0 
1 12 0 
2 2 1 2 0 

result:

ok ok

Test #14:

score: 0
Accepted
time: 0ms
memory: 15548kb

input:

27 36

output:

14
0 
2 1 1 1 0 
2 4 1 9 1 
1 5 1 
2 6 0 8 1 
1 7 1 
1 1 1 
2 2 1 2 0 
1 10 0 
1 11 0 
2 12 0 13 1 
2 2 1 2 0 
1 14 0 
1 1 0 

result:

ok ok

Test #15:

score: 0
Accepted
time: 0ms
memory: 15688kb

input:

55 84

output:

19
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 6 1 12 1 
1 7 1 
2 8 0 11 1 
1 9 1 
1 10 1 
1 1 1 
2 3 1 3 0 
1 13 0 
2 14 0 15 1 
2 4 1 4 0 
1 16 0 
2 17 0 18 1 
2 2 1 2 0 
1 19 0 
1 1 0 

result:

ok ok

Test #16:

score: 0
Accepted
time: 0ms
memory: 15500kb

input:

297208 929600

output:

70
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
2 20 1 44 1 
2 21 0 43 1 
2 22 0 42 1 
1 23 1 
2 24 0 41 1 
2 25 0 40 1 
2 26 0 39 1 
1 27 ...

result:

ok ok

Test #17:

score: 0
Accepted
time: 0ms
memory: 15584kb

input:

45728 589156

output:

67
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
5 20 1 36 1 37 1 38 1 39 1 
2 21 0 35 1 
1 22 1 
1 23 1 
2 24 0 34 1 
2 25 0 33 1 
1 26 1 
...

result:

ok ok

Test #18:

score: 0
Accepted
time: 0ms
memory: 15620kb

input:

129152 138000

output:

48
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 14 1 27 1 
1 15 1 
1 16 1 
1 17 1 
1 18 1 
1 19 1 
2 20 0 26 1 
2 21 0 25 1 
2 22 0 24 1 
1 23 1 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
1 28 0 
1 29 0 
1 30 0 ...

result:

ok ok

Test #19:

score: 0
Accepted
time: 0ms
memory: 15624kb

input:

245280 654141

output:

68
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
3 20 1 37 1 38 1 
1 21 1 
1 22 1 
2 23 0 36 1 
1 24 1 
1 25 1 
1 26 1 
1 27 1 
1 28 1 
2 29...

result:

ok ok

Test #20:

score: 0
Accepted
time: 0ms
memory: 15568kb

input:

202985 296000

output:

63
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 17 1 43 1 
1 18 1 
2 19 0 42 1 
2 20 0 41 1 
2 21 0 40 1 
1 22 1 
1 23 1 
2 24 0 39 1 
2 25 0 38 1 
2 26 0 37 1 
1 27 1 
1 28 1 ...

result:

ok ok

Test #21:

score: 0
Accepted
time: 4ms
memory: 15568kb

input:

438671 951305

output:

69
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
2 20 1 46 1 
1 21 1 
2 22 0 45 1 
1 23 1 
2 24 0 44 1 
1 25 1 
1 26 1 
2 27 0 43 1 
2 28 0 ...

result:

ok ok

Test #22:

score: 0
Accepted
time: 2ms
memory: 15568kb

input:

425249 739633

output:

71
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 19 1 46 1 
1 20 1 
2 21 0 45 1 
2 22 0 44 1 
1 23 1 
1 24 1 
1 25 1 
1 26 1 
1 27 1 
2 28 0 43 1 
1 29...

result:

ok ok

Test #23:

score: 0
Accepted
time: 0ms
memory: 15588kb

input:

551207 961718

output:

75
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
1 19 1 
2 20 0 48 1 
2 21 0 47 1 
2 22 0 46 1 
2 23 0 45 1 
1 24 1 
1 25 1 
2 26 0 44 1 
1 27 1 
2 28 0 ...

result:

ok ok

Test #24:

score: 0
Accepted
time: 0ms
memory: 15520kb

input:

114691 598186

output:

74
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
4 20 1 48 1 49 1 50 1 
1 21 1 
1 22 1 
2 23 0 47 1 
2 24 0 46 1 
2 25 0 45 1 
2 26 0 44 1 
...

result:

ok ok

Test #25:

score: 0
Accepted
time: 0ms
memory: 15588kb

input:

234654 253129

output:

57
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
1 15 1 
1 16 1 
1 17 1 
2 18 0 38 1 
2 19 0 37 1 
1 20 1 
2 21 0 36 1 
1 22 1 
2 23 0 35 1 
2 24 0 34 1 
1 25 1 
2 26 0 33 1 
2 27 0 32 1 
1 28 1 
1 29 1 
1...

result:

ok ok

Test #26:

score: 0
Accepted
time: 1ms
memory: 15636kb

input:

554090 608599

output:

61
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
1 17 1 
1 18 0 
1 19 0 
2 20 0 43 1 
2 21 0 42 1 
1 22 1 
1 23 1 
1 24 1 
2 25 0 41 1 
1 26 1 
2 27 0 40 1 
2 28 0 39 1 
2 29 0 38...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed