QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#439824#8769. Champernowne SubstringHKOI0#WA 749ms3828kbC++143.2kb2024-06-12 19:09:252024-06-12 19:09:25

Judging History

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

  • [2024-06-12 19:09:25]
  • 评测
  • 测评结果:WA
  • 用时:749ms
  • 内存:3828kb
  • [2024-06-12 19:09:25]
  • 提交

answer

#include <bits/stdc++.h>
#define all(a) begin(a), end(a)
#define int __int128_t
using namespace std;

string to_string(int x){
	if (x == 0) {
		return "0";
	} else if (x < 0) {
		return "-" + to_string(x);
	}
	string res;
	while (x) {
		res.push_back('0' + x % 10);
		x /= 10;
	}
	assert(res.size());
	reverse(res.begin(), res.end());
	return res;
}

ostream& operator<< (ostream& out, int x){
	return out << to_string(x);
}

int f(int x){
	--x;
	int pw = 1, b = 1;
	int res = 0;
	while (x >= pw) {
		int l = pw, r = min(x, pw * 10 - 1);
		res += b * (r - l + 1);
		pw *= 10; ++b;
	}
	return res + 1;
}



string g(int pos, int len){
	--pos;
	int pw = 1, b = 1;
	while (pos >= pw * b * 9) {
		pos -= pw * b * 9;
		pw *= 10; ++b;
	}

	string t;
	assert(pos / b + pw > 0);
	int base = pos / b + pw, rem = pos % b;
	while (t.size() < len + 50) {
		t += to_string(base); ++base;
	}
	return t.substr(rem, len);
}

int to_int(string s){
	int res = 0;
	for (auto c : s) {
		res = res * 10 + (c - '0');
	}
	return res;
}

bool matched(string s, string t){
	if (s.size() != t.size()) return false;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '?') continue;
		if (s[i] != t[i]) return false;
	}
	return true;
}

int ans;
string s; 
void test(int x){
	if (x <= 0) return;
	// cout << x << ' ' << g(x, s.size()) << endl;
	if (matched(s, g(x, s.size()))) {
		ans = min(ans, x);
	}
}

bool can(string& s, int idx, char c){
	if (s[idx] == '?') return true;
	return s[idx] == c;
}

string superimpose(string& s, int l){
	string r(l, '?');
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '?') continue;
		if (r[i % l] == '?') {
			r[i % l] = s[i];
		} else if (r[i % l] != s[i]) {
			r[i % l] = 'X';
		}
	}
	return r;
}

void solve() {
	cin >> s;
	ans = (__int128_t) 1 << 120;
	
	for (int pw10 = 1; pw10 < 1e26; pw10 *= 10) {
		int x = f(pw10);
		for (int y = -50; y <= 50; y++) {
			test(x + y);
		}
	}
	for (int i = 1; i <= 10000; i++) {
		test(i);
	}
	for (int l = 3; l <= 25; l++) {
		for (int pad = 0; pad < l; pad++) {
			string t = string(pad, '?') + s;
			int rem = l - t.size() % l;
			t += string(rem, '?');
			assert(t.size() % l == 0);
			assert(t.size() / l <= 10);

			int n = t.size();
			for (int i = 0; i < n / l; i++) {
				for (int c = 0; c < l; c++) {
					for (int x = 0; x <= 8; x++) {
						string u; u.push_back('0' + x);
						for (int i = 0; i < c; i++) {
							u.push_back('9');
						}
						bool ok = true;
						for (int j = l - u.size(); j < l; j++) {
							ok &= can(t, i * l + j, u[j - (l - u.size())]);
						}
						if (!ok) continue;
						string La = superimpose(t, l).substr(0, l - c - 1);
						for (auto c : La) {
							if (!c) ok = false;
						}
						if (!ok) continue;
						int y = to_int(La);
						y = y * 10 + x;
						for (int j = 0; j < c; j++) {
							y = y * 10 + 9;
						}
						test(f(y) - i * l + pad);
					}
				}
			}
		}
	}
	const int MOD = 998244353;
	cout << ans % MOD << '\n';
}

int32_t main(){
#ifndef LOCAL
	cin.tie(0)->sync_with_stdio(false);
#endif
	int64_t t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 437ms
memory: 3828kb

input:

9
0
???1
121
1?1?1
??5?54?50?5?505?65?5
000000000000
?2222222
?3????????9??8???????1??0
9?9??0????????????2

output:

11
7
14
10
314159
796889014
7777
8058869
38886

result:

ok 9 lines

Test #2:

score: 0
Accepted
time: 749ms
memory: 3620kb

input:

10
0000000000000000000000000
0000000?002100000000000?0
6999?999?999999989?999999
0???0?1000?0??000?????0?1
9??9?999998?9?999999100?0
96?9997999?8999991????010
99?99??999999999??????99?
?0?0000?00000000?0210?0?0
99?999?999?99?9??999?9?9?
9?????9?99?99??9??99??9??

output:

545305036
574985081
788888865
5889591
902934046
488873
902034054
830780534
68888820
5882870

result:

ok 10 lines

Test #3:

score: -100
Wrong Answer
time: 513ms
memory: 3612kb

input:

10
23573?0208935200503593500
08?9?1188980?661?18161467
22000103111010?24490??02?
4?129184?3644311331226625
9014217281609919609168?18
27809?1808?34646796569990
5116137658333853138917519
8778798398090800698?93888
742?9472125?9529272277272
5260238541343?22235629222

output:

500292333
500292333
500292333
500292333
194206422
500292333
452740345
92216689
500292333
363629923

result:

wrong answer 1st lines differ - expected: '108802929', found: '500292333'