QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#688508#9519. Build a ComputerZeroSkyAC ✓1ms3896kbC++202.6kb2024-10-30 10:21:452024-10-30 10:21:45

Judging History

This is the latest submission verdict.

  • [2024-10-30 10:21:45]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3896kb
  • [2024-10-30 10:21:45]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int MAX = 1100;
unordered_map<int, int> mp;
int L, R;
int cnt = 2;
int S = 1, T = 2;
int l[MAX], r[MAX];

int tree[MAX][5];
vector<pair<int, int> > Se;

int lowbit(int x) {
	return x & -x;
}

void print2(int x) {
	if (x <= 1) {
		cout << x;
	} else {
		print2(x / 2);
		cout << x % 2;
	}
}

int ta[50], tb[50], lim1, lim2;
void get(int a, int b) {
	lim2 = 0;
	while (a) {
		ta[++lim2] = a & 1;
		a >>= 1;
	}
	lim2 = 0;
	while (b) {
		tb[++lim2] = b & 1;
		b >>= 1;
	}

	for (int i = lim2; i >= 1; i--) {
		if (ta[i] == tb[i]) {
			lim1 = i;
		} else break;
	}
}

int main() {
//	cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
	mp[1] = T;
	cin >> L >> R;
	int tmp = 0;
	int now = L;
	for (int i = L; i <= R;) {
//		cout<<i<<endl;
		l[++tmp] = i, r[tmp] = (i + lowbit(i)) - 1;
		i = i + lowbit(i);
		if (i <= R)
			now = i;
	}
	tmp--;
	
//	cout<<"now:"<<now<<endl;
	
	while (now < R) {
		l[++tmp] = now;
		int t = 0;
		while (now + (1 << t) - 1 <= R) t++;
		t--;
		now += (1 << t);
		r[tmp] = now - 1;
	}
	if (now == R) l[++tmp] = R, r[tmp] = R;

//	for(int i = 1; i <= tmp; i++){
//		print2(l[i]); puts("");
//		print2(r[i]); puts(""); puts("");
//	}

	for (int i = 1; i <= tmp; i++) {
		
		get(l[i], r[i]);
		
		if(l[i] == 1){
			Se.push_back({T, 1});
			continue;
		}
		int f = 0;
		
		int p = S;
		if(i == 1 || (int)log2(l[i]) != (int)log2(l[i - 1]))
			Se.push_back({++cnt, 1}), tree[p][1] = cnt, f = 1, p = cnt;
		
		for (int j = lim2 - f; j >= lim1; j--) {
			if (j == 1) {
				if (!tree[p][ta[j]]) tree[p][ta[j]] = T;
			}
			else if (!tree[p][ta[j]]) {
				tree[p][ta[j]] = ++cnt;
				p = cnt;
			} else p = tree[p][ta[j]];
		}
		if (lim1 > 1) {
			if (mp[lim1 - 1] != 0) {
				mp[lim1] = p;
				tree[p][2] = mp[lim1 - 1];
			} else {
				int tt = 1;
				while (mp[lim1 - tt] == 0) {
					mp[lim1 - tt + 1] = p;
					tree[p][2] = ++cnt;
					p = cnt;
					tt++;
				}
				tree[p][2] = mp[lim1 - tt];
				mp[lim1 - tt + 1] = p;
			}
		}
	}
	cout<<cnt<<endl;
	cout << Se.size() << " ";
	for (int i = 0; i < (int)Se.size(); i++) {
		cout<<Se[i].first<<" "<<Se[i].second<<" ";
	}
	cout<<endl;
	for (int i = 2; i <= cnt; i++) {
		if(tree[i][2]){
			cout<<2<<" "<<tree[i][2]<<" "<<1<<" "<<tree[i][2]<<" "<<0<<endl;
		}
		else if(tree[i][1] && tree[i][0]){
			cout<<2<<" "<<tree[i][1]<<" "<<1<<" "<<tree[i][0]<<" "<<0<<endl;
		}
		else if(tree[i][0]){
			cout<<1<<" "<<tree[i][0]<<" "<<0<<endl;
		}
		else if(tree[i][1]){
			cout<<1<<" "<<tree[i][1]<<" "<<1<<endl;
		}
		else cout<<0<<endl;
	}
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 7

output:

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

result:

ok ok

Test #2:

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

input:

10 27

output:

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

result:

ok ok

Test #3:

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

input:

5 13

output:

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

result:

ok ok

Test #4:

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

input:

1 1000000

output:

45
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: 3624kb

input:

1 1

output:

2
1 2 1 
0

result:

ok ok

Test #6:

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

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

input:

3 7

output:

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

result:

ok ok

Test #8:

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

input:

1 5

output:

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

result:

ok ok

Test #9:

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

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

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

input:

7 51

output:

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

result:

ok ok

Test #12:

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

input:

51 79

output:

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

result:

ok ok

Test #13:

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

input:

92 99

output:

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

result:

ok ok

Test #14:

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

input:

27 36

output:

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

result:

ok ok

Test #15:

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

input:

55 84

output:

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

result:

ok ok

Test #16:

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

input:

297208 929600

output:

61
2 3 1 35 1 
0
2 34 1 4 0
2 32 1 5 0
1 6 1
2 31 1 7 0
2 30 1 8 0
2 28 1 9 0
1 10 1
2 27 1 11 0
2 26 1 12 0
2 21 1 13 0
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
2 19 1 19 0
2 20 1 20 0
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 18 1 18 0
2 21 1 21 0
2 26 1 26 0
2 29 1 29 0
2 27 1 27 0
2 ...

result:

ok ok

Test #17:

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

input:

45728 589156

output:

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

result:

ok ok

Test #18:

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

input:

129152 138000

output:

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

result:

ok ok

Test #19:

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

input:

245280 654141

output:

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

result:

ok ok

Test #20:

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

input:

202985 296000

output:

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

result:

ok ok

Test #21:

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

input:

438671 951305

output:

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

result:

ok ok

Test #22:

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

input:

425249 739633

output:

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

result:

ok ok

Test #23:

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

input:

551207 961718

output:

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

result:

ok ok

Test #24:

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

input:

114691 598186

output:

61
4 3 1 32 1 36 1 37 1 
0
1 4 1
1 5 1
2 31 1 6 0
2 30 1 7 0
2 29 1 8 0
2 28 1 9 0
2 27 1 10 0
2 26 1 11 0
2 25 1 12 0
2 24 1 13 0
2 23 1 14 0
2 22 1 15 0
2 21 1 16 0
2 19 1 17 0
1 18 1
1 2 1
2 20 1 20 0
2 2 1 2 0
2 19 1 19 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 #25:

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

input:

234654 253129

output:

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

result:

ok ok

Test #26:

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

input:

554090 608599

output:

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

result:

ok ok

Extra Test:

score: 0
Extra Test Passed