UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185135#3303. xorYansuan_HCl100728ms9156kbC++111.5kb2023-09-23 09:40:082023-09-23 12:00:20

answer

#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline))
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;

//const int SZ(1 << 23);
//unsigned char buf[SZ], *S, *Q;
//#define getchar() ((S==Q)&&(Q=buf+fread(S=buf,1,SZ,stdin)),S==Q?EOF:*S++)
template <typename T>
void rd(T& s) {
	int c = getchar();
	T f = 1; s = 0;
	while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
	while (isdigit(c)) { s = s * 10 + (c ^ 48); c = getchar(); }
	s *= f;
}
template <typename T, typename... Y>
void rd(T& x, Y&... y) { rd(x), rd(y...); }
template <typename T>
void pr(T s, bool f = 1) {
    if (s < 0) { printf("-"); s = -s; }
    if (!s) return void(f ? printf("0") : 0);
    pr(s / 10, 0);
    printf("%d", (signed)(s % 10));
}
#define meow(...) fprintf(stderr, __VA_ARGS__)

const int N = 1048576;
int n, m, a[N], b[N], f[N], lim;
void sum() {
	for (int i = 1; (1 << i) <= lim; ++i)
		for (int k = 0; k < (1 << (i - 1)); ++k)
			for (int j = 0; j + k + (1 << (i - 1)) <= lim; j += (1 << i))
				a[j + k + (1 << (i - 1))] ^= a[j + k];
}

int main() {
	rd(n, m); U (i, 0, n - 1) rd(a[i]), b[i] = a[i] ^ (i ? b[i - 1] : 0);
	printf("%d ", b[n - 1]);
	reverse(a, a + n);
	lim = 1;
	while (lim <= n || lim <= m) lim <<= 1;
//	lim = 16384;
	sum();
	
	U (i, 1, m - 1)
		printf("%d ", a[(lim - 1) & (~i)]);
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1168kb

input:

1000 1000
147366708 372984783 795004506 1029660805 838354648 526116849 623114704 967641624 76288123 ...

output:

902994770 960950138 502237924 65588273 532002922 429363699 446656541 840669003 457107364 618988765 1...

result:

ok single line: '902994770 960950138 502237924 ...5 804581752 51931816 402607532 '

Test #2:

score: 10
Accepted
time: 0ms
memory: 1168kb

input:

1000 1000
65623956 153535227 892994980 849870763 68675037 955785258 423217055 661613196 557888647 46...

output:

878581059 455483040 175190676 452432166 553293522 469065052 217177202 806453507 909617062 524132535 ...

result:

ok single line: '878581059 455483040 175190676 ... 667177817 143126443 497242830 '

Test #3:

score: 10
Accepted
time: 0ms
memory: 1168kb

input:

1000 1000
1057623028 1007827495 990985454 670080720 372737251 311711843 223319406 355584768 10394891...

output:

719127800 596344307 786689572 213591930 1005373695 576788768 594200807 38989697 743083574 388729656 ...

result:

ok single line: '719127800 596344307 786689572 ... 861157164 544409444 217156393 '

Test #4:

score: 10
Accepted
time: 22ms
memory: 2060kb

input:

100000 100000
9449784 303889875 416314253 693514818 1023584014 843464434 538183667 458263442 1248282...

output:

1067185538 652982242 63804762 711958526 438154385 756396557 374155426 644015252 777033056 177474217 ...

result:

ok single line: '1067185538 652982242 63804762 ... 612823959 255536322 302198666 '

Test #5:

score: 10
Accepted
time: 24ms
memory: 2060kb

input:

100000 100000
1001448856 84440319 514304726 513724776 253904403 199391019 338286018 152235014 494083...

output:

875377186 87788492 187224223 998168347 961762262 610160865 530711195 134388600 865836757 613041139 7...

result:

ok single line: '875377186 87788492 187224223 9... 453516142 711454891 386014344 '

Test #6:

score: 10
Accepted
time: 23ms
memory: 2060kb

input:

100000 100000
919706104 938732588 612295200 333934734 557966617 629059428 138388369 919948410 975683...

output:

920122372 951644158 461324910 713985762 105537977 83565671 154217674 375666722 195620633 766033493 5...

result:

ok single line: '920122372 951644158 461324910 ... 816490741 552834479 417442485 '

Test #7:

score: 10
Accepted
time: 21ms
memory: 2060kb

input:

100000 100000
837963352 719283032 710285674 154144691 862028830 1058727837 1012232545 613919982 3835...

output:

80253624 658480877 636945162 159350861 582947300 887381610 300799149 344466655 301903488 453501772 3...

result:

ok single line: '80253624 658480877 636945162 1... 233638940 424056158 279214042 '

Test #8:

score: 10
Accepted
time: 220ms
memory: 9152kb

input:

1000000 1000000
6309065 807032563 875904490 844606676 297343196 567420073 593985515 731319264 971310...

output:

255787649 43788334 958918633 568438522 647334103 971838429 456802318 892311485 709030532 400656434 5...

result:

ok single line: '255787649 43788334 958918633 5... 322163864 289512492 268773622 '

Test #9:

score: 10
Accepted
time: 201ms
memory: 9156kb

input:

1000000 1000000
998308137 587583008 973894963 664816634 601405409 997088482 394087866 425290836 3791...

output:

614764413 1014734125 924615770 913615190 613574741 878666807 639820385 73806012 885233360 160145458 ...

result:

ok single line: '614764413 1014734125 924615770... 998847432 920308764 695449812 '

Test #10:

score: 10
Accepted
time: 217ms
memory: 9152kb

input:

1000000 1000000
251583231 882325500 857949844 384664415 516518423 349385835 996471793 952010760 2512...

output:

507328463 864381380 614965309 251857277 839061907 240130984 267325549 897479997 565946437 323948419 ...

result:

ok single line: '507328463 864381380 614965309 ...498457740 784634982 1053651380 '