QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#700221	#9519. Build a Computer	TheZone	AC ✓	1ms	3884kb	C++23	2.2kb	2024-11-02 12:24:30	2024-11-02 12:24:30

Judging History

This is the latest submission verdict.

[2024-11-02 12:24:30]
Judged

Verdict: AC
Time: 1ms
Memory: 3884kb

Show

[2024-11-02 12:24:30]
Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=1e5+10;
int L,R,mx,st,ct,to[N][2];
vector< pair<int,int> >gg,e[N];
inline void build(int l,int r,int ll,int rr){
	if (ll<=l && r<=rr){
		gg.push_back({l,r});
		mx=max(mx,__lg(r-l+1));
		return;
	}
	if (ll<=mid) build(l,mid,ll,rr);
	if (mid<rr) build(mid+1,r,ll,rr);
}
inline void add(int u,int v,int w){
	e[u].emplace_back(v,w);
}
inline void cons(int x,int y){
	vector<int>V;
	while (x) V.push_back(x%2),x>>=1;
	reverse(V.begin(),V.end());
	int la=st,sz=V.size();
	rep(i,0,sz-1)
		if (i!=sz-1){
			if (!to[la][V[i]]) to[la][V[i]]=++ct,add(la,ct,V[i]);
			la=to[la][V[i]];
		}
		else add(la,y,V[i]);
}
inline void solve(){
	cin>>L>>R;
	build(0,(1<<20)-1,L,R);
	rep(i,2,mx+1) add(i-1,i,0),add(i-1,i,1);
	st=mx+2,ct=st;
	for (auto i:gg){
		int L=i.first,R=i.second,g=__lg(R-L+1);
		cons((L>>g),mx+1-g);
	}
	cout<<ct<<'\n';
	rep(i,1,ct){
		cout<<e[i].size()<<' ';
		for (auto j:e[i]) cout<<j.first<<' '<<j.second<<' ';
		cout<<'\n';
	}
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    while (t--) solve();
    return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=1e5+10;
int L,R,mx,st,ct,to[N][2];
vector< pair<int,int> >gg,e[N];
inline void build(int l,int r,int ll,int rr){
	if (ll<=l && r<=rr){
		gg.push_back({l,r});
		mx=max(mx,__lg(r-l+1));
		return;
	}
	if (ll<=mid) build(l,mid,ll,rr);
	if (mid<rr) build(mid+1,r,ll,rr);
}
inline void add(int u,int v,int w){
	e[u].emplace_back(v,w);
}
inline void cons(int x,int y){
	vector<int>V;
	while (x) V.push_back(x%2),x>>=1;
	reverse(V.begin(),V.end());
	int la=st,sz=V.size();
	rep(i,0,sz-1)
		if (i!=sz-1){
			if (!to[la][V[i]]) to[la][V[i]]=++ct,add(la,ct,V[i]);
			la=to[la][V[i]];
		}
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    while (t--) solve();
    return 0;
}*/

源文件, 语言: C++23

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3588kb

input:

5 7

output:

result:

ok ok

Test #2:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

10 27

output:

8
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
0 
1 6 1 
4 7 0 2 1 1 0 8 1 
1 3 1 
1 2 0

result:

ok ok

Test #3:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

5 13

output:

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

result:

ok ok

Test #4:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

1 1000000

output:

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

result:

ok ok

Test #5:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

1 1

output:

2
0 
1 1 1

result:

ok ok

Test #6:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

7 9

output:

result:

ok ok

Test #7:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

3 7

output:

result:

ok ok

Test #8:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

1 5

output:

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

result:

ok ok

Test #9:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

1 4

output:

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

result:

ok ok

Test #10:

score: 0

Accepted

time: 1ms

memory: 3884kb

input:

8 9

output:

result:

ok ok

Test #11:

score: 0

Accepted

time: 1ms

memory: 3812kb

input:

7 51

output:

9
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
2 5 0 5 1 
0 
3 7 1 2 1 1 1 
2 8 1 1 0 
2 5 1 9 0 
1 3 0

result:

ok ok

Test #12:

score: 0

Accepted

time: 1ms

memory: 3656kb

input:

51 79

output:

result:

ok ok

Test #13:

score: 0

Accepted

time: 1ms

memory: 3584kb

input:

92 99

output:

result:

ok ok

Test #14:

score: 0

Accepted

time: 0ms

memory: 3660kb

input:

27 36

output:

result:

ok ok

Test #15:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

55 84

output:

result:

ok ok

Test #16:

score: 0

Accepted

time: 1ms

memory: 3684kb

input:

297208 929600

output:

53
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
2 5 0 5 1 
2 6 0 6 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
2 10 0 10 1 
2 11 0 11 1 
2 12 0 12 1 
2 13 0 13 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
2 17 0 17 1 
2 18 0 18 1 
2 19 0 19 1 
0 
1 21 1 
4 22 0 2 1 1 0 36 1 
2 23 0 3 1 
1 24 1 
2 25 0 5 1 
2 26 0 6 1 
2 2...

result:

ok ok

Test #17:

score: 0

Accepted

time: 1ms

memory: 3816kb

input:

45728 589156

output:

47
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
2 5 0 5 1 
2 6 0 6 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
2 10 0 10 1 
2 11 0 11 1 
2 12 0 12 1 
2 13 0 13 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
2 17 0 17 1 
2 18 0 18 1 
2 19 0 19 1 
0 
4 21 1 3 1 2 1 1 1 
2 22 0 5 1 
2 23 1 31 0 
1 24 1 
2 25 0 8 1 
2 26 0 9 1 ...

result:

ok ok

Test #18:

score: 0

Accepted

time: 1ms

memory: 3880kb

input:

129152 138000

output:

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

result:

ok ok

Test #19:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

245280 654141

output:

49
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
2 5 0 5 1 
2 6 0 6 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
2 10 0 10 1 
2 11 0 11 1 
2 12 0 12 1 
2 13 0 13 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
2 17 0 17 1 
2 18 0 18 1 
2 19 0 19 1 
0 
2 21 1 1 1 
2 22 1 33 0 
1 23 1 
2 24 0 5 1 
1 25 1 
1 26 1 
1 27 1 
1 28 1 ...

result:

ok ok

Test #20:

score: 0

Accepted

time: 0ms

memory: 3656kb

input:

202985 296000

output:

51
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
2 5 0 5 1 
2 6 0 6 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
2 10 0 10 1 
2 11 0 11 1 
2 12 0 12 1 
2 13 0 13 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
0 
1 18 1 
2 19 1 35 0 
2 20 0 1 1 
2 21 0 2 1 
2 22 0 3 1 
1 23 1 
1 24 1 
2 25 0 6 1 
2 26 0 7 1 
2 27 0 8 1 
1 28 1...

result:

ok ok

Test #21:

score: 0

Accepted

time: 1ms

memory: 3660kb

input:

438671 951305

output:

54
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
2 5 0 5 1 
2 6 0 6 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
2 10 0 10 1 
2 11 0 11 1 
2 12 0 12 1 
2 13 0 13 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
2 17 0 17 1 
2 18 0 18 1 
2 19 0 19 1 
0 
1 21 1 
2 22 1 1 0 
4 23 0 3 1 2 0 39 1 
1 24 1 
2 25 0 5 1 
1 26 1 
1 27 1 ...

result:

ok ok

Test #22:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

425249 739633

output:

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

result:

ok ok

Test #23:

score: 0

Accepted

time: 1ms

memory: 3584kb

input:

551207 961718

output:

56
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
2 5 0 5 1 
2 6 0 6 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
2 10 0 10 1 
2 11 0 11 1 
2 12 0 12 1 
2 13 0 13 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
2 17 0 17 1 
2 18 0 18 1 
0 
1 20 1 
2 21 0 39 1 
2 22 0 1 1 
2 23 0 2 1 
2 24 0 3 1 
1 25 1 
1 26 1 
2 27 0 6 1 
1 28...

result:

ok ok

Test #24:

score: 0

Accepted

time: 1ms

memory: 3856kb

input:

114691 598186

output:

54
2 2 0 2 1 
2 3 0 3 1 
2 4 0 4 1 
2 5 0 5 1 
2 6 0 6 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
2 10 0 10 1 
2 11 0 11 1 
2 12 0 12 1 
2 13 0 13 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
2 17 0 17 1 
2 18 0 18 1 
2 19 0 19 1 
0 
3 21 1 2 1 1 1 
2 22 1 37 0 
1 23 1 
2 24 0 6 1 
2 25 0 7 1 
2 26 0 8 1 
2 2...

result:

ok ok

Test #25:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

234654 253129

output:

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

result:

ok ok

Test #26:

score: 0

Accepted

time: 1ms

memory: 3588kb

input:

554090 608599

output:

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

result:

ok ok

Extra Test:

score: 0

Extra Test Passed