QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#309934#8129. Binary Sequenceucup-team484#AC ✓36ms12784kbC++171006b2024-01-20 22:49:512024-01-20 22:49:51

Judging History

你现在查看的是最新测评结果

  • [2024-01-20 22:49:51]
  • 评测
  • 测评结果:AC
  • 用时:36ms
  • 内存:12784kb
  • [2024-01-20 22:49:51]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
vector<string> arr;

void solve() {
	ll n, m; cin >> n >> m;
	for (int i = 0; i < size(arr) && i < n; i++) {
		if (size(arr[i]) > m && (i + 1) % 2 == n % 2) {
			cout << arr[i][size(arr[i]) - m - 1] << "\n";
			return;
		}
	}
	cout << "0\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	arr.push_back("1");
	for (int i = 1;; i++) {
		string s;
		for (int j = 0, jj = 0; j < size(arr[i - 1]); j = jj) {
			while (jj < size(arr[i - 1]) && arr[i - 1][j] == arr[i - 1][jj])
				jj++;
			int x = jj - j;
			for (int k = 31 - __builtin_clz(x); k >= 0; k--)
				s.push_back('0' + ((x >> k) & 1));
			s.push_back(arr[i - 1][j]);
		}
		arr.push_back(s);
		if (size(arr[i - 1]) > N)
			break;
	}
	int t; cin >> t; while (t--) solve();
}

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

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 12720kb

input:

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

output:

1
1
0
1
1
1
0
1
1
0

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 7ms
memory: 12784kb

input:

10
28 69772
10 7908
4 3198
4 85913
14 52729
3 20445
9 88912
17 23743
25 37356
2 97697

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 15ms
memory: 12576kb

input:

100
29 110358
18 13645
18 590344
36 550462
11 133055
8 769352
11 265432
7 158530
12 29189
2 830361
11 584395
31 693707
7 879812
19 25069
21 616926
3 85158
31 675739
17 118385
24 315535
29 59615
10 33445
17 609235
8 738138
20 209540
4 287616
32 522302
26 959741
5 453537
27 74313
28 296289
28 857972
2...

output:

0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 36ms
memory: 12612kb

input:

100000
702433635413308636 962533
864089450531108488 538792
262747333715821506 454514
859830947243984718 105219
365621373252206174 447331
890829905503831899 507146
116987306031929573 154370
157986473366693144 364746
502917586764426513 49981
874588963478161584 594867
467219058104100510 790503
11034861...

output:

1
1
1
1
1
1
1
0
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
1
0
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
1
0
0
1
0
0
1
0
1
1
1
1
1
1
1
0
1
1
1
0
0
0
1
1
1
0
1
1
1
1
1
1
0
1
0
1
1
1
0
0
0
1
0
0
1
0
1
1
1
1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
1
1
0
1
1
0
1
0
0
0
1
1
0
1
1
0
0
1
1
1
1
1
0
0
0
0
0
0
1
1
1
0
0
1
...

result:

ok 100000 numbers

Extra Test:

score: 0
Extra Test Passed