QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#318349#7877. Balanced ArrayNetwork_ErrorTL 0ms0kbC++142.1kb2024-01-31 09:07:012024-01-31 09:07:02

Judging History

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

  • [2024-01-31 09:07:02]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-01-31 09:07:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
#define ull unsigned long long
namespace Maths {
	const int mod = 998244353;
	int power(int x, int y) {
		int ans = 1; while (y) {
			if (y & 1) ans = 1ll * ans * x % mod; y >>= 1; x = 1ll * x * x % mod;
		} return ans;
	}
	int power(int x, int y, int mod) {
		int ans = 1; while (y) {
			if (y & 1) ans = 1ll * ans * x % mod; y >>= 1; x = 1ll * x * x % mod;
		} return ans;
	}
	int fac[1000010], inv[1000010];
	void init() {
		fac[0] = fac[1] = inv[0] = inv[1] = 1;
		for (int i = 2; i <= 1e6; i++) fac[i] = 1ll * fac[i - 1] * i % mod, inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
		for (int i = 2; i <= 1e6; i++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
	}
	int binom(int n, int m) {
		return n < m || m < 0 ? 0 : 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
	}
} using namespace Maths;
const ull base = 10111; ull bpow[2000010], hsh[2000010];
namespace Loser {
	int n, a[2000010]; bool ans[2000010];
	int get(char c) {
		return isdigit(c) ? c - '0' : c >= 'a' ? c - 'a' + 10 : c - 'A' + 36;
	}
	ull hash(int l, int r) {
		return hsh[r] - hsh[l - 1] * bpow[r - l + 1];
	}
	bool chk(int k, int l) {
		if (k > (l - 1) / 2) return 1;
		return hash(1, l - 2 * k) + hash(1 + 2 * k, l) == 2 * hash(1 + k, l - k);
	}
	void main() {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			char c = getchar();
			while (c != ' ' && c != '\n') a[i] = a[i] * 62 + get(c), c = getchar();
			hsh[i] = hsh[i - 1] * base + a[i];
		}
		for (int k = 1, l = 0; k <= n; k++) {
			while (l < n && chk(k, l + 1)) {
				++l; ans[l] = k <= (l - 1) / 2;
			}
		}
		for (int i = 1; i <= n; i++) cout << ans[i]; cout << '\n';
	}
}
signed main() {
	bpow[0] = 1;
	for (int i = 1; i <= 2e6; i++) bpow[i] = bpow[i - 1] * base;
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1; while (T--) Loser::main(); return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

3
1 2 3

output:


result: