QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#574013#2519. Number with BachelorslifanWA 595ms14668kbC++141.2kb2024-09-18 20:34:432024-09-18 20:34:44

Judging History

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

  • [2024-09-18 20:34:44]
  • 评测
  • 测评结果:WA
  • 用时:595ms
  • 内存:14668kb
  • [2024-09-18 20:34:43]
  • 提交

answer

// 
#include<bits/stdc++.h>
typedef unsigned long long ull;
ull dp[21][65536];
int a[21],len,B;
ull dfs(int dep,int s,bool pre,bool lim){
	if(!dep)return 1;
	if(!lim&&!pre&&~dp[dep][s])return dp[dep][s];
	ull res=0;
	const int up=lim?a[dep]:B-1;
	for(int i=0;i<=up;++i)
		if(!(s>>i&1))
			if(pre&(!i))res+=dfs(dep-1,0,true,lim&(!a[dep]));
			else res+=dfs(dep-1,s|(1<<i),false,lim&(i==a[dep]));
	if(!lim&&!pre)dp[dep][s]=res;
	return res;
}
inline ull solve(ull n){
	len=0;
	for(ull i=n;i;i/=B)a[++len]=i%B;
	return dfs(len,0,true,true);
}
int T;
ull l,r;
int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%d",&T);
	for(char tp,op;T--;){
		scanf("\n %c %c",&tp,&op);
		B=tp=='d'?10:16;
		if(op=='0'){
			scanf(tp=='d'?"%llu%llu":"%llx%llx",&l,&r);
			printf(tp=='d'?"%llu\n":"%llx\n",solve(r)-(l?solve(l-1):0));
		}else{
			static ull x,res;
			scanf(tp=='d'?"%llu":"%llx",&x);
			if(x>(tp=='d'?8877691:53319412081141)){
				puts("-");
				continue;
			}
			if(x==1){
				puts("0");
				continue;
			}
			l=0;r=0xffffffffffffffff;
			while(l<=r){
				ull mid=l+(r-l>>1);
				if(solve(mid)>=x)res=mid,r=mid-1;
				else l=mid+1;
			}
			printf(tp=='d'?"%llu\n":"%llx\n",res);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 37ms
memory: 14668kb

input:

6
d 0 10 20
h 0 10 1f
d 1 10
h 1 f
d 1 1000000000
h 1 ffffffffffffffff

output:

10
f
9
e
-
-

result:

ok 6 lines

Test #2:

score: -100
Wrong Answer
time: 595ms
memory: 14584kb

input:

50000
h 1 147a
d 0 25 71
d 1 3587
d 0 26922 51887
d 1 711
d 0 3 5
h 0 7bf2defab442a0b1 f299a4cf1d4d9bed
d 0 6961 91018
d 1 4
d 1 876
h 1 12cc5d3370f99120
d 1 161315
h 0 25f 6959
d 0 467 516
d 1 298
h 1 70260cdc2da73281
h 1 928e17d65d764ca2
h 1 c8ec8a7b67605e51
d 1 91697
d 0 4941925161850941148 89850...

output:

1b36
73
1985
89436
400
3
747d603f500
273650
3
482
-
52000
4681
154
200
-
-
-
30000
0
1
47
-
140000
1
1
-
15b4
175f
8a996855000
124b7
6279
9
1894
-
39be22a900
43361820300
146ce
2a55
-
0
-
7
d
6
2041
-
c2fbb33300
0
5
98573
270000
500
389
0
-
2ac838aa480
2506
1678286
7
-
-
1e6
0
0
48b6
9
-
2b0
72027
14...

result:

wrong answer 2nd lines differ - expected: '43', found: '73'