QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745148#8769. Champernowne Substringcyj888WA 91ms3860kbC++144.4kb2024-11-14 07:25:562024-11-14 07:25:57

Judging History

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

  • [2024-11-14 07:25:57]
  • 评测
  • 测评结果:WA
  • 用时:91ms
  • 内存:3860kb
  • [2024-11-14 07:25:56]
  • 提交

answer

#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second 
#define pb push_back
#define ott(i, l, r) for (__int128 i = (l); i <= (r); i ++)
#define tto(i, l, r) for (__int128 i = (r); i >= (l); i --)
using namespace std;
typedef long long ll;
typedef long double ld;
int read () {
	int x = 0; bool f = false; char c = getchar ();
	while (!isdigit (c)) f |= (c == '-'), c = getchar ();
	while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
	return f ? -x : x;
}
const int N = 1e6 + 110, mod = 998244353;
int T, n, m, k; __int128 res;
string str, sum;
vector <int> a, val;
inline string get (__int128 x) {
	string ret = "";
	while (x) ret += x % 10 + '0', x /= 10;
	reverse (ret.begin (), ret.end ());
	return ret;
}
inline __int128 cnt (__int128 x) {
	__int128 ret = 0, now = 1; int c = 0;
	while (now <= x / 10) ret += 9 * now * (++ c), now *= 10;
	ret += (x - now + 1) * (++ c);
	return ret;
}
inline void upd (const __int128 &v) {
    return void (res = (!res || res > v) ? v : res);
}
void sol () {
	cin >> str, n = str.size ();
	sum = ""; ott (i, 1, 99999) sum += get (i);
	//我tm想X人了:)
	m = sum.size (); ott (i, 0, m - n) {//暴力去除位数<=5的
		bool ok = true;
		ott (j, 0, n - 1) if (str[j] ^ '?' && str[j] ^ sum[i + j]) {
			ok = false; break;
		}
		if (ok) upd (i + 1);
	}
	__int128 now = 10; ott (l, 2, 26) {//存在边界
		now *= 10; __int128 pre = cnt (now - 11);
		sum = ""; ott (i, now - 10, now + 10) sum += get (i); 
		m = sum.size (); ott (i, 0, m - n) {
			bool ok = true;
			ott (j, 0, n - 1) 
				if (str[j] ^ '?' && str[j] ^ sum[i + j]) {
					ok = false; break;
				}
			if (ok) upd (pre + i + 1);//, printf ("l = %d, i = %d\n", (int)l, (int)i);
		}
	}
	//不存在边界,即位数均为l>=5的情况
	ott (l, 5, 26) {//不进位
		ott (v, 1, 9) {
			ott (i, 1, l - 1) a.pb (-i);
			a.pb (v);
		}
		m = a.size (); ott (i, 0, m - n) {
			bool ok = true; val.resize (l + 1, -1);
			ott (j, 0, n - 1) {
				if (!(str[j] ^ '?')) continue;
				if (a[i + j] < 0) {
					if (!~val[-a[i + j]]) val[-a[i + j]] = str[j];
					else if (val[-a[i + j]] ^ str[j]) ok = false;
				}
				else if (a[i + j] + '0' ^ str[j]) ok = false;
			}
			if (!(val[1] ^ '0')) ok = false;
			if (ok) {
				ott (j, 1, l - 1) if (!~val[j]) val[j] = '0' + (j == 1); 
				val[l] = '1', now = 0;
				ott (j, 1, l) now = 10 * now + val[j] - '0';
				upd (cnt (now - 1) + i + 1);
			} 
			val.clear ();
		} 
		a.clear ();
	}
	ott (l, 5, 26) {//有且仅有一个数进位,因为这些数最多5,6个
		ott (c, 1, l - 1) {//枚举一次进了多少位/末9的连续个数
			ott (v, 5, 9) {
				ott (i, 1, l - c - 1) a.pb (-i);
				a.pb (-(l - c + 1));
				ott (i, 1, c - 1) a.pb (9);
				a.pb (v);
			}
			ott (v, 0, 5) {
				ott (i, 1, l - c) a.pb (-i);
				ott (i, 1, c - 1) a.pb (0);
				a.pb (v);
			}
			m = a.size (); ott (i, 0, m - n) {
				bool ok = true; val.resize (l + 1, -1);
				ott (j, 0, n - 1) {
					if (!(str[j] ^ '?')) continue;
					if (a[i + j] < 0) {
						if (!~val[-a[i + j]]) val[-a[i + j]] = str[j];
						else if (val[-a[i + j]] ^ str[j]) ok = false;
					}
					else if (a[i + j] + '0' ^ str[j]) ok = false;
				}
				// if (ok) cout << (int)l << " " << (int)c << " " << ok << endl;//, getchar ();
				if (!~val[l - c] && !~val[l - c + 1]) {
					val[l - c] = '1' + (l - c == 1),
					val[l - c + 1] = '0' + (l - c == 1);
				}
				else if (~val[l - c] && ~val[l - c + 1]) {
					if (val[l - c] ^ val[l - c + 1] + 1) {
						ok = false;
					}
				}
				else if (~val[l - c]) {
					if (val[l - c] ^ '0') val[l - c + 1] = val[l - c] - 1;
					else ok = false;
				}
				else {
					if (val[l - c + 1] ^ '9') val[l - c] = val[l - c + 1] + 1;
					else ok = false;
				}
				if (!(val[1] ^ '0')) ok = false;
				if (ok) {
					ott (j, 1, l - c - 1) if (!~val[j]) val[j] = '0' + (j == 1);
					ott (j, l - c + 1, l) val[j] = '0'; now = 0;
					ott (j, 1, l) now = 10 * now + val[j] - '0';
					// if (now < 0) {
					// 	cout << (int)(l - c) << endl;
					// 	ott (j, 1, l) cout << (char)val[j]; cout << endl;getchar ();
					// }
					upd (cnt (now - 1) - 5 * l + i + 1);
				} 
				val.clear ();
			}
			a.clear ();
		} 
	}
	cout << (int)(res % mod) << endl, res = 0;
	return ;
}
int main () {
	ios :: sync_with_stdio (false);
	cin.tie (0), cout.tie (0);
	cin >> T; while (T --) sol ();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 91ms
memory: 3860kb

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: -100
Wrong Answer
time: 89ms
memory: 3752kb

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
788888870
488873
902034054
830780534
68888820
5882870

result:

wrong answer 5th lines differ - expected: '902934046', found: '788888870'