| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
My solution: each bit is independent so let us consider them separately.
Now notice that if the first row and colmn are already filled, the whole grid is uniquely determined.
Use a dsu to maintain the equality relationship between the positions and the final time complexity is $$$\mathcal O((n + q) \log V \alpha n)$$$.
I have tested the code in mashups and it runs 2499ms, which means that the constant is too big. Can any one help me to optimize the code?
Given $$$q \; (q \le 2 \cdot 10^5)$$$ operations:
$$$|a|,|b|,|x|,|y| \le 10^6$$$.
We call a string $$$s$$$ of length $$$n$$$ good, if and only if $$$n \bmod 2 = 0$$$ and $$$s[1,\dfrac{n}{2}] = s[\dfrac{n}{2}+1,n]$$$ (i.e. there exists a string $$$t$$$ that $$$s = t + t$$$.)
You are given a string $$$s$$$. For each $$$r \in [1,n]$$$:
Is the guess correct?
We transform the condition $$$s_i \ne s_{n-i+1}$$$ into if we change all $$$\texttt{0} \to \texttt{1},\texttt{1} \to \texttt{0}$$$ and reverse it to get a string $$$t$$$, $$$s$$$ is good if and only if $$$s = t$$$. Then we can use suffix array or manachar to get the answer.
Then, the hash solution did the same transformation and use hashing to get the answer with $$$\text{base} = 10^9+7$$$ and $$$\text{mod} = 2^{64}-1$$$ (unsigned long long). Can it be hacked? I have done stress test for $$$15000$$$ test cases :(
I will provide the hash code and the suffix array code below, if you need to make a stress test.
Is there any extension which can change the submissions status such as changing Wrong answer on test X to Wonderful answer on test X? If it exists where can I find it?
