QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#702077	#5981. Costly Binary Search	Luzexi	0	81ms	10116kb	C++14	957b	2024-11-02 15:15:08	2024-11-02 15:15:08

Judging History

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

[2024-11-02 15:15:08]
评测

测评结果：0
用时：81ms
内存：10116kb

查看

[2024-11-02 15:15:08]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,a[N];
char s[N];
namespace sub3{
	int L[10][N],R[10][N];
	void solve(){
		for(int val = 0;val<=180;++val){
			int now = val % 10;
			for(int i = 0;i<=n;++i)L[now][i] = R[now][i] = i;
			for(int i = 1;i<=n;++i)if(a[i] <= val){
				int tl = L[(val - a[i]) % 10][i-1], tr = R[(val - a[i]) % 10][i];
				L[now][tr] = min(L[now][tr],tl);
				R[now][tl] = max(R[now][tl],tr);
			}
			for(int i = n-1;~i;--i)L[now][i] = min(L[now][i+1],L[now][i]);
			for(int i = 1;i<=n;++i)R[now][i] = max(R[now][i-1],R[now][i]);
			if(L[now][n] <= 1 || R[now][1] >= n)return printf("%d",val),void();
		}
		assert(0);
	}
}

void work(){
	scanf("%s",s+1), n = strlen(s+1);
	for(int i = 1;i<=n;++i)a[i] = s[i] - 48;
	sub3::solve();
	puts("");
}

int main(){
	int T; scanf("%d",&T);
	for(int cas = 1;cas <= T;++cas){
		printf("Case #%d: ",cas);
		work();
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 81ms

memory: 10116kb

input:

50
8
5128831164925953487661279378526736416489768154389124821528467927357884749642747626797857463132866343496157991453139582295398452863172464853698678624523849653538713928372648295734165346972222781179687541337591976277864785653638476127839556323849395641196246971351933655287441377531627938395427487...

output:

Case #1: 0
Case #2: 37
Case #3: 34
Case #4: 37
Case #5: 34
Case #6: 114
Case #7: 126
Case #8: 24
Case #9: 37
Case #10: 103
Case #11: 36
Case #12: 64
Case #13: 37
Case #14: 117
Case #15: 37
Case #16: 35
Case #17: 14
Case #18: 34
Case #19: 36
Case #20: 37
Case #21: 38
Case #22: 39
Case #23: 14
Case #2...

result:

wrong answer 1st lines differ - expected: 'Case #1: 8', found: 'Case #1: 0'

Subtask #2:

score: 0

Runtime Error

Test #2:

score: 0

Runtime Error

input:

50
647322722753778843259213887674615134214258235986992692879314555957455541351526284343217116351733247781713552149464672262787737941588358671583528664757823365936975517145283412965139791726299864122725212222496898855627124979178341548651669956711341742838725446489235961853391195148929571712449139335...