QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353486#6510. Best Carry Player 3Zxc200611#WA 16ms3840kbC++141.4kb2024-03-14 10:01:572024-03-14 10:01:57

Judging History

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

  • [2024-03-14 10:01:57]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:3840kb
  • [2024-03-14 10:01:57]
  • 提交

answer

/*
若 x>y,可以交换 x、y。那么设 x<y。
设 2^t <= k < 2^(t+1)。
2 次 xor 操作可以凑出 0...2^(t+1)-1 的任何数。
若 x,y <= 2^(t+1)-1,则答案小于等于 2。
否则先用至多 2 次操作把 x 的最后 0...t 位变为全 1(能 1 次肯定好),然后加 1,
然后再用至多 2 次操作把 x 的最后 0...t 位变为全 1,然后加 1。
...直到 x 的 t+1 位及以上与 y 相同。然后再用至多两次操作。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int bitFloor(int k) // get max t that 2^t<=k
{
	int t=0;
	while((1LL<<(t+1))<=k)
		t+=1;
	return t;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		int x,y,k;
		cin>>x>>y>>k;
		if(x>y)
			swap(x,y);
		if(k==0)
		{
			cout<<y-x<<'\n';
			continue;
		}
		int t=bitFloor(k);
		// cout<<"t="<<t<<endl;
		int sx=x&((1LL<<(t+1))-1),lx=(x-sx)>>(t+1);
		int sy=y&((1LL<<(t+1))-1),ly=(y-sy)>>(t+1);
		// cout<<"sx="<<sx<<" lx="<<lx<<" sy="<<sy<<" ly="<<ly<<endl;
		function<int(int,int)> solveSmall=[&](int sx,int sy)
		{
			return sx==sy?0:((sx^sy)<=k?1:2);
		};
		if(lx==ly)
		{
			cout<<solveSmall(sx,sy)<<'\n';
			continue;
		}
		int ans=solveSmall(sx,(1LL<<(t+1))-1)+1;
		lx+=1,sx=0;
		ans+=(ly-lx)*(solveSmall(sx,(1LL<<(t+1))-1)+1);
		ans+=solveSmall(sx,sy);
		cout<<ans<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

8
4 5 0
5 8 3
9 2 6
15 28 5
97 47 8
164 275 38
114514 1919 810
0 1152921504606846975 1

output:

1
2
3
5
11
6
331
1152921504606846975

result:

ok 8 numbers

Test #2:

score: -100
Wrong Answer
time: 16ms
memory: 3840kb

input:

100000
84 318 6
54 226 7
92 33 0
39 54 5
76 79 7
247 110 0
211 90 0
4 430 3
230 17 1
491 93 5
196 117 7
137 29 2
76 490 6
422 43 7
277 26 4
159 43 1
67 37 5
17 2 5
113 176 7
85 473 0
68 217 7
275 8 7
124 34 1
30 66 0
80 149 3
103 149 6
84 354 1
27 342 7
94 114 1
69 125 1
72 48 7
361 8 7
285 82 1
74 ...

output:

87
45
59
6
1
137
121
213
213
150
21
81
156
95
95
116
12
6
16
388
39
67
90
36
35
17
270
79
20
56
6
89
203
108
26
15
157
98
111
389
174
123
59
289
78
17
21
36
275
191
17
102
60
93
100
11
6
79
44
63
91
60
22
109
11
3
10
67
11
85
207
47
39
83
156
189
107
27
81
247
81
335
33
144
11
50
54
347
233
175
30
7...

result:

wrong answer 809th numbers differ - expected: '1', found: '2'