QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#679159#9519. Build a Computerucup-team134#AC ✓1ms4148kbC++171.9kb2024-10-26 17:01:302024-10-26 17:01:32

Judging History

This is the latest submission verdict.

  • [2024-10-26 17:01:32]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4148kb
  • [2024-10-26 17:01:30]
  • Submitted

answer

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;

mt19937 rng(time(NULL));

const int N=101;
vector<vector<pair<int,int>>> graf(N);
int trc;
int gt(){
	return trc++;
}
int mxp=1,gde=2;
map<int,int> pwc;
int gtp(int r){
	while(mxp-1<r){
		int sl=gt();
		graf[sl].pb({gde,1});
		graf[sl].pb({gde,0});
		mxp*=2;
		gde=sl;
		pwc[mxp-1]=gde;
	}
	assert(pwc[r]!=0);
	return pwc[r];
}
map<int,int> pws;
vector<int> firsts;
int solve(int l,int r,int bt,bool first){
	//printf("%i %i %i %i\n",l,r,bt,first);
	if(bt>r){
		if(first)
			return solve(l,r,bt/2,first);
		else{
			int my=gt();
			int sl=solve(l,r,bt/2,first);
			graf[my].pb({sl,0});
			return my;
		}
	}
	if(l==0&&pws[r]){ // endcase
		assert(!first);
		return gtp(r);
	}
	//printf("%i %i %i\n",l,r,bt);
	if(bt<=l){
		if(first){
			int sl=solve(l-bt,r-bt,bt/2,0);
			firsts.pb(sl);
			return 1;
		}
		int my=gt();
		int sl=solve(l-bt,r-bt,bt/2,0);
		graf[my].pb({sl,1});
		return my;
	}
	if(first){
		int lft=solve(l,bt-1,bt/2,1);
		assert(lft==1);
		int rght=solve(0,r-bt,bt/2,0);
		firsts.pb(rght);
		return 1;
	}
	int my=gt();
	int lft=solve(l,bt-1,bt/2,0);
	int rght=solve(0,r-bt,bt/2,0);
	graf[my].pb({lft,0});
	graf[my].pb({rght,1});
	return my;
}
int main()
{
	int l,r;
	cin >> l >> r;
	int en=2;
	pwc[0]=en;
	trc=en+1;
	for(int i=0;i<21;i++){
		pws[(1<<i)-1]=1;
	}
	int bt=1<<20;
	assert(solve(l,r,bt,1)==1);
	for(auto p:firsts){
		graf[1].pb({p,1});
	}
	printf("%i\n",trc-1);
	for(int i=1;i<trc;i++){
		printf("%i",sz(graf[i]));
		for(auto p:graf[i]){
			printf(" %i %i",p.f,p.s);
		}
		printf("\n");
	}
	return 0;
}

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

詳細信息

Test #1:

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

input:

5 7

output:

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

result:

ok ok

Test #2:

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

input:

10 27

output:

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

result:

ok ok

Test #3:

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

input:

5 13

output:

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

result:

ok ok

Test #4:

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

input:

1 1000000

output:

39
20 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 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 18 1 18 0
2 19 1 19 0
...

result:

ok ok

Test #5:

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

input:

1 1

output:

2
1 2 1
0

result:

ok ok

Test #6:

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

input:

7 9

output:

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

result:

ok ok

Test #7:

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

input:

3 7

output:

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

result:

ok ok

Test #8:

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

input:

1 5

output:

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

result:

ok ok

Test #9:

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

input:

1 4

output:

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

result:

ok ok

Test #10:

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

input:

8 9

output:

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

result:

ok ok

Test #11:

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

input:

7 51

output:

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

result:

ok ok

Test #12:

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

input:

51 79

output:

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

result:

ok ok

Test #13:

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

input:

92 99

output:

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

result:

ok ok

Test #14:

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

input:

27 36

output:

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

result:

ok ok

Test #15:

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

input:

55 84

output:

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

result:

ok ok

Test #16:

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

input:

297208 929600

output:

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

result:

ok ok

Test #17:

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

input:

45728 589156

output:

49
5 3 1 28 1 29 1 30 1 31 1
0
2 4 0 26 1
1 5 1
1 6 1
2 7 0 23 1
2 8 0 22 1
1 9 1
2 10 0 20 1
1 11 1
2 12 0 18 1
1 17 1
2 2 1 2 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 18 1 18 0
2 19 1 19 0
2 20 1 20 0
2 21 1 21 0
2 22 1 22 0
2 23 1 23 0
2 24 1 24 0
2 25 1 25 0
2 26 1 26 0
2 ...

result:

ok ok

Test #18:

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

input:

129152 138000

output:

40
2 3 1 22 1
0
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
2 9 0 21 1
2 10 0 20 1
2 11 0 19 1
1 18 1
2 2 1 2 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 18 1 18 0
2 19 1 19 0
2 20 1 20 0
1 23 0
1 24 0
1 25 0
1 26 0
2 28 0 29 1
2 21 1 21 0
2 27 1 27 0
2 27 0 30 1
1 31 0
2 20 0 32 1...

result:

ok ok

Test #19:

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

input:

245280 654141

output:

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

result:

ok ok

Test #20:

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

input:

202985 296000

output:

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

result:

ok ok

Test #21:

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

input:

438671 951305

output:

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

result:

ok ok

Test #22:

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

input:

425249 739633

output:

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

result:

ok ok

Test #23:

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

input:

551207 961718

output:

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

result:

ok ok

Test #24:

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

input:

114691 598186

output:

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

result:

ok ok

Test #25:

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

input:

234654 253129

output:

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

result:

ok ok

Test #26:

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

input:

554090 608599

output:

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

result:

ok ok

Extra Test:

score: 0
Extra Test Passed