QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#682124#9519. Build a ComputerAsritAC ✓0ms4172kbC++141.6kb2024-10-27 14:02:502024-10-27 14:02:51

Judging History

This is the latest submission verdict.

  • [2024-10-27 14:02:51]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 4172kb
  • [2024-10-27 14:02:50]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rop(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define por(i,a,b) for(int i=(a);i>(b);i--)
using namespace std;
const int N=110;
int l,r;
int cnt[2],len,dig[2][N];
int id,s,t,rfl[N];
vector<int> tomid[N],c[N];
queue<int> ans[N];

void adde(int fa,int x,int w){
	ans[fa].push(x),ans[fa].push(w);
}

void addcommon(){
	int la=id;
	por(i,cnt[1],len) adde(la,++id,dig[1][i]),la=id;
}

void add(int opt){
	int la=s;
	per(i,len,1){
		if(cnt[opt]>=i) adde(la,i!=1?++id:t,dig[opt][i]);
		if(i!=len&&dig[opt][i]==opt) tomid[la].push_back(i),c[la].push_back(opt^1);
		la=id;
	}
}

void output(){
	printf("%d\n",id);
	rep(i,1,id){
		printf("%d ",ans[i].size()/2);
		while(!ans[i].empty()) printf("%d ",ans[i].front()),ans[i].pop();
		puts("");
	}
}

int main(){
	scanf("%d%d",&l,&r);
	int p=0;
	if(l==r) p=1;
	while(l) dig[0][++cnt[0]]=l&1,l>>=1;
	while(r) dig[1][++cnt[1]]=r&1,r>>=1;
	len=cnt[1];
	if(p==1){
		t=1,s=id=2,add(0);
		output();
		return 0;
	}
	if(cnt[0]==cnt[1]){
		per(i,cnt[0],1){
			if(dig[0][i]==dig[1][i]) --len;
			else break;
		}
	}
	t=1,id=2;
	addcommon();
	s=id;
	add(0),add(1);
	int maxlen=0,la=rfl[1]=t;
	rep(i,1,id)
		rop(j,0,tomid[i].size())
			maxlen=max(maxlen,tomid[i][j]);
	rep(i,2,maxlen){
		rfl[i]=++id;
		adde(id,la,0),adde(id,la,1);
		la=id;
	}
	rep(i,1,id)
		rop(j,0,tomid[i].size())
			adde(i,rfl[tomid[i][j]],c[i][j]);
	output();
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3844kb

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: 3884kb

input:

10 27

output:

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

result:

ok ok

Test #3:

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

input:

5 13

output:

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

result:

ok ok

Test #4:

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

input:

1 1000000

output:

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

result:

ok ok

Test #5:

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

input:

1 1

output:

2
0 
1 1 1 

result:

ok ok

Test #6:

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

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: 0ms
memory: 3884kb

input:

3 7

output:

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

result:

ok ok

Test #8:

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

input:

1 5

output:

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

result:

ok ok

Test #9:

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

input:

1 4

output:

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

result:

ok ok

Test #10:

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

input:

8 9

output:

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

result:

ok ok

Test #11:

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

input:

7 51

output:

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

result:

ok ok

Test #12:

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

input:

51 79

output:

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

result:

ok ok

Test #13:

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

input:

92 99

output:

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

result:

ok ok

Test #14:

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

input:

27 36

output:

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

result:

ok ok

Test #15:

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

input:

55 84

output:

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

result:

ok ok

Test #16:

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

input:

297208 929600

output:

57
0 
2 3 1 21 1 
2 4 0 56 1 
2 5 0 55 1 
1 6 1 
2 7 0 53 1 
2 8 0 52 1 
2 9 0 51 1 
1 10 1 
2 11 0 49 1 
2 12 0 48 1 
2 13 0 47 1 
1 14 1 
1 15 1 
1 16 1 
1 17 1 
1 18 1 
2 19 0 41 1 
2 20 0 40 1 
2 1 0 1 1 
2 22 1 57 0 
2 23 1 56 0 
1 24 0 
1 25 0 
1 26 0 
2 27 1 52 0 
1 28 0 
2 29 1 50 0 
2 30 1 ...

result:

ok ok

Test #17:

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

input:

45728 589156

output:

54
0 
5 3 1 18 1 54 1 53 1 52 1 
2 4 0 50 1 
1 5 1 
1 6 1 
2 7 0 47 1 
2 8 0 46 1 
1 9 1 
2 10 0 44 1 
1 11 1 
2 12 0 42 1 
1 13 1 
2 14 0 40 1 
2 15 0 39 1 
2 16 0 38 1 
2 17 0 37 1 
2 1 0 1 1 
1 19 0 
1 20 0 
1 21 0 
2 22 1 51 0 
2 23 1 50 0 
2 24 1 49 0 
2 25 1 48 0 
2 26 1 47 0 
2 27 1 46 0 
1 2...

result:

ok ok

Test #18:

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

input:

129152 138000

output:

47
0 
2 3 1 19 1 
1 4 1 
1 5 1 
1 6 1 
1 7 1 
1 8 1 
2 9 0 45 1 
2 10 0 44 1 
2 11 0 43 1 
1 12 1 
2 13 0 41 1 
2 14 0 40 1 
2 15 0 39 1 
2 16 0 38 1 
2 17 0 37 1 
2 18 0 36 1 
2 1 0 1 1 
1 20 0 
1 21 0 
1 22 0 
1 23 0 
2 24 1 47 0 
2 25 1 46 0 
1 26 0 
2 27 1 44 0 
2 28 1 43 0 
1 29 0 
1 30 0 
1 31...

result:

ok ok

Test #19:

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

input:

245280 654141

output:

56
0 
3 3 1 20 1 56 1 
1 4 1 
1 5 1 
2 6 0 52 1 
1 7 1 
1 8 1 
1 9 1 
1 10 1 
1 11 1 
2 12 0 46 1 
2 13 0 45 1 
2 14 0 44 1 
1 15 1 
2 16 0 42 1 
2 17 0 41 1 
2 18 0 40 1 
2 19 0 39 1 
2 1 0 1 1 
1 21 0 
1 22 0 
2 23 1 54 0 
2 24 1 53 0 
2 25 1 52 0 
2 26 1 51 0 
2 27 1 50 0 
2 28 1 49 0 
1 29 0 
2 ...

result:

ok ok

Test #20:

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

input:

202985 296000

output:

52
0 
2 3 1 20 1 
1 4 1 
2 5 0 52 1 
2 6 0 51 1 
2 7 0 50 1 
1 8 1 
1 9 1 
2 10 0 47 1 
2 11 0 46 1 
2 12 0 45 1 
1 13 1 
1 14 1 
1 15 1 
2 16 0 41 1 
1 17 1 
2 18 0 39 1 
2 19 0 38 1 
1 1 1 
1 21 0 
1 22 0 
2 23 1 52 0 
1 24 0 
1 25 0 
1 26 0 
1 27 0 
2 28 1 47 0 
1 29 0 
1 30 0 
1 31 0 
2 32 1 43 ...

result:

ok ok

Test #21:

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

input:

438671 951305

output:

57
0 
2 3 1 21 1 
1 4 1 
2 5 0 55 1 
1 6 1 
2 7 0 53 1 
1 8 1 
1 9 1 
2 10 0 50 1 
2 11 0 49 1 
2 12 0 48 1 
1 13 1 
1 14 1 
2 15 0 45 1 
2 16 0 44 1 
2 17 0 43 1 
1 18 1 
1 19 1 
1 20 1 
1 1 1 
2 22 1 57 0 
2 23 1 56 0 
1 24 0 
2 25 1 54 0 
1 26 0 
1 27 0 
1 28 0 
1 29 0 
2 30 1 49 0 
1 31 0 
1 32 ...

result:

ok ok

Test #22:

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

input:

425249 739633

output:

56
0 
2 3 1 21 1 
1 4 1 
2 5 0 55 1 
2 6 0 54 1 
1 7 1 
1 8 1 
1 9 1 
1 10 1 
1 11 1 
2 12 0 48 1 
1 13 1 
2 14 0 46 1 
2 15 0 45 1 
1 16 1 
2 17 0 43 1 
2 18 0 42 1 
2 19 0 41 1 
2 20 0 40 1 
1 1 1 
1 22 0 
2 23 1 56 0 
2 24 1 55 0 
1 25 0 
2 26 1 53 0 
1 27 0 
1 28 0 
2 29 1 50 0 
1 30 0 
1 31 0 
...

result:

ok ok

Test #23:

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

input:

551207 961718

output:

56
0 
1 3 1 
2 4 0 22 1 
2 5 0 56 1 
2 6 0 55 1 
2 7 0 54 1 
1 8 1 
1 9 1 
2 10 0 51 1 
1 11 1 
2 12 0 49 1 
2 13 0 48 1 
1 14 1 
2 15 0 46 1 
2 16 0 45 1 
1 17 1 
2 18 0 43 1 
2 19 0 42 1 
1 20 1 
1 21 1 
1 1 1 
2 23 1 56 0 
1 24 0 
2 25 1 54 0 
1 26 0 
2 27 1 52 0 
1 28 0 
2 29 1 50 0 
2 30 1 49 0...

result:

ok ok

Test #24:

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

input:

114691 598186

output:

55
0 
4 3 1 19 1 55 1 54 1 
1 4 1 
1 5 1 
2 6 0 50 1 
2 7 0 49 1 
2 8 0 48 1 
2 9 0 47 1 
2 10 0 46 1 
2 11 0 45 1 
2 12 0 44 1 
2 13 0 43 1 
2 14 0 42 1 
2 15 0 41 1 
2 16 0 40 1 
2 17 0 39 1 
1 18 1 
1 1 1 
1 20 0 
1 21 0 
2 22 1 53 0 
1 23 0 
1 24 0 
2 25 1 50 0 
1 26 0 
1 27 0 
1 28 0 
1 29 0 
1...

result:

ok ok

Test #25:

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

input:

234654 253129

output:

46
0 
1 3 1 
1 4 1 
1 5 1 
2 6 0 20 1 
2 7 0 46 1 
1 8 1 
2 9 0 44 1 
1 10 1 
2 11 0 42 1 
2 12 0 41 1 
1 13 1 
2 14 0 39 1 
2 15 0 38 1 
1 16 1 
1 17 1 
1 18 1 
1 19 1 
2 1 0 1 1 
1 21 0 
2 22 1 45 0 
2 23 1 44 0 
2 24 1 43 0 
1 25 0 
1 26 0 
2 27 1 40 0 
2 28 1 39 0 
1 29 0 
1 30 0 
2 31 1 36 0 
1...

result:

ok ok

Test #26:

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

input:

554090 608599

output:

52
0 
1 3 1 
1 4 0 
1 5 0 
2 6 0 22 1 
2 7 0 52 1 
1 8 1 
1 9 1 
1 10 1 
2 11 0 48 1 
1 12 1 
2 13 0 46 1 
2 14 0 45 1 
2 15 0 44 1 
1 16 1 
1 17 1 
2 18 0 41 1 
1 19 1 
2 20 0 39 1 
1 21 1 
2 1 0 1 1 
1 23 0 
2 24 1 51 0 
1 25 0 
1 26 0 
2 27 1 48 0 
1 28 0 
1 29 0 
2 30 1 45 0 
1 31 0 
2 32 1 43 0...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed