# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Congrats nightcrawler0112 for hitting the 200000000-th submission! Sadly it wasn't an AC...
I want to rename my handle to FireGhost, which was occupied by this 4-year-inactive guy (link).
As far as I know from this post (link), I can request a handle of an inactive participant. Sorry for pinging you, MikeMirzayanov, but can you please take a look at my request? Thank you so much!
Sparky_Master_WCH1226 would be really disappointed when he put a lot of efforts into shitposting but still lost his last place in one night
Thank you for participating in the contest! We hope you enjoy the problems. You can also give feedback on each problem, it will help us much in future problem settings. By the way, feel free to share your solution!
How will you solve this problem if there are just $$$2$$$ male cosplayers?
Notice the distance between $$$2$$$ consecutive male cosplayers.
It is easy to see, in a beautiful picture, there must be at least $$$2$$$ female cosplayers between $$$2$$$ consecutive male cosplayers. It is also the sufficient condition, as if there are $$$x$$$ male cosplayers in a subsegment, there are at least $$$2(x - 1) = 2x - 2 \geq x$$$ for all $$$x \geq 2$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
string s;
vector<int> v;
void solve() {
v.clear();
cin >> n >> s;
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '0') v.push_back(i);
}
for (int i = 0; i < (int)v.size() - 1; ++i) {
if (v[i + 1] - v[i] <= 2) ans += 2 - (v[i + 1] - v[i]) + 1;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while (t--) solve();
}
t = int(input())
for _ in range(t):
n = input()
s = input()
ans = 0
cnt = 2
for c in s:
if c == '1': cnt += 1
else:
ans += max(2 - cnt, 0)
cnt = 0
print(ans)
1658B - Марин и не взаимно простая перестановка
Let's $$$ g = \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) $$$. What is the maximum value of $$$g$$$?
For each value of $$$g$$$, can you construct a satisfying permutation?
We can prove that $$$g \leq 2$$$.
Assuming $$$g > 2$$$:
If there exists a prime number $$$p > 2$$$ that $$$p \mid g$$$, there are $$$\left \lfloor \dfrac{n}{p} \right \rfloor$$$ numbers divisible by $$$p$$$, so we can match at most $$$2 \left \lfloor \dfrac{n}{3} \right \rfloor$$$ numbers into pairs, which is smaller than $$$n$$$.
Otherwise, we can match odd numbers with even positions, and even numbers with odd positions, which leads to $$$2 \mid g$$$. Because $$$p_2$$$ is odd, $$$2 \cdot p_2$$$ is not divisible by $$$2^k$$$ with $$$k > 1$$$.
Therefore, $$$g\leq 2$$$.
Therefore:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
void solve() {
int n; cin >> n;
if (n & 1) {
cout << "0\n";
return;
}
long long ans = 1;
for (int i = 1; i <= n / 2; ++i) {
ans *= 1LL * i * i % MOD;
ans %= MOD;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while (t--) solve();
return 0;
}
MOD = 998244353
t = int(input())
for _ in range(t):
n = int(input())
if n & 1:
print(0)
continue
ans = 1
for i in range(1, n // 2 + 1):
ans = ans * i % MOD
ans = ans * ans % MOD
print(ans)
1658C - Синдзю и потерянная перестановка
There is exactly one $$$1$$$ in array $$$c$$$ (in $$$(i - 1)$$$-th cyclic shift, $$$c_i > 1$$$ if $$$p_1 \neq n$$$, and $$$c_i = 1$$$ if $$$p_1 = n$$$), so if the number of $$$1s$$$ is greater or less than one, the answer is $$$\texttt{NO}$$$.
We can rotate the array such that $$$c_1 = 1$$$ (initial state) because we don't have to construct the permutation, so if there exists a permutation with $$$p_1 = n$$$, the answer is $$$\texttt{YES}$$$.
Notice the difference of $$$c_i$$$ and $$$c_{i + 1}$$$.
In the $$$i$$$-th cyclic shift, if $$$p_1 > p_2$$$ then $$$c_{i + 1} \leq c_i$$$, otherwise $$$c_{i + 1} - c_i = 1$$$, so if there exists a position $$$i$$$ such that $$$c_{i + 1} - c_i > 1$$$, the answer is $$$\texttt{NO}$$$.
This is the sufficient condition. It can be shown that, if $$$c_{i + 1} - c_i \leq 1$$$ for all $$$1 \leq i < n$$$, then there exists a permutation that satisfies.
Here is a sketch of the construction: https://codeforces.me/blog/entry/101302?#comment-899523
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int &v: a) cin >> v;
if (count(a.begin(), a.end(), 1) != 1) {
cout << "NO\n";
return;
}
int p = find(a.begin(), a.end(), 1) - a.begin();
rotate(a.begin(), a.begin() + p, a.end());
for (int i = 1; i < n; ++i) {
if (a[i] - a[i - 1] > 1) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while (t--) solve();
return 0;
}
import sys
input = sys.stdin.readline
t = int(input())
for _ in range (t):
n = int(input())
a = list(map(int, input().split()))
if a.count(1) != 1:
print("NO")
continue
a.append(a[0])
ok = True
for i in range (0, n):
if a[i + 1] - a[i] > 1:
ok = False
break
if ok: print("YES")
else: print("NO")
1658D1 - 388535 (упрощенная версия)
Let's look at the binary representation of numbers from $$$0$$$ to $$$7$$$:
Let us look at the $$$i$$$-th bit only (maybe $$$i=2$$$), we will get a sequence like $$$[0,0,1,1,0,0,1,1]$$$. Notice that the number of zeroes equals the number of ones in a prefix only when the length of the prefix is a multiple of $$$2^i$$$. Otherwise, there will be more zeros than ones.
So, we will count the number of flipped and unflipped bits for each bit position.
However, if the number of ones is equal to the number of zeros, we can assign the $$$i$$$-th bit anything we like. The rough sketch of the proof is that if $$$x$$$ is inside $$$a$$$ then $$$x\oplus2^i$$$ is also inside $$$a$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int p[N], cnt[32][2];
void solve() {
memset(cnt, 0, sizeof cnt);
int l, r; cin >> l >> r;
for (int i = l; i <= r; ++i) {
int x; cin >> x;
for (int j = 0; j <= 30; ++j, x >>= 1)
cnt[j][x & 1]++;
}
int ans = 0;
for (int i = 0; i <= 30; ++i) {
ans |= ((cnt[i][0] < cnt[i][1]) * (1 << i));
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while (t--) solve();
return 0;
}
import sys
input = sys.stdin.readline
t = int(input())
for _ in range (t):
l, r = map(int, input().split())
a = list(map(int, input().split()))
cnt = [[0] * 2 for _ in range (32)]
for x in a:
for i in range (31):
cnt[i][x & 1] += 1
x >>= 1
ans = 0
for i in range (31):
if (cnt[i][0] < cnt[i][1]):
ans |= (1 << i)
print(ans)
1658D2 - 388535 (усложненная версия)
If $$$a \oplus b = 1$$$, then $$$(a \oplus x) \oplus (b \oplus x) = 1$$$.
if $$$l$$$ is even and $$$r$$$ is odd, the last bit of $$$x$$$ can be either $$$0$$$ or $$$1$$$ (we can pair $$$a_i$$$ with $$$a_i \oplus 1$$$).
There are two solutions to this problem.
If $$$l$$$ is even and $$$r$$$ is odd, we can skip the last bit and divide the range by two, then recursively solve it. Otherwise, we will pair $$$a_i$$$ with $$$a_i \oplus 1$$$, and we will left with at most $$$2$$$ candidates for $$$x$$$ to check.
There is also another solution: we can iterate all possibilities of $$$x$$$ (by assuming $$$a_i$$$ is $$$l \oplus x$$$ for all $$$1 \leq i \leq n$$$). If $$$x$$$ is the hidden number, $$$l \leq a_i \oplus x \leq r$$$ for all $$$1 \leq i \leq n$$$, so the problem reduce to "count the number of $$$a_i$$$ that $$$l \leq a_i \oplus x \leq r$$$", which can be solved with binary trie.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], l, r;
set <int> s, s2;
void solve() {
int mul = 1;
s.clear();
cin >> l >> r;
for (int i = l; i <= r; ++i) {
cin >> a[i];
s.insert(a[i]);
}
for (; l % 2 == 0 && r % 2 == 1; l >>= 1, r >>= 1, mul <<= 1) {
s2.clear();
for (int i: s) s2.insert(i >> 1);
swap(s, s2);
}
int ans;
if (l % 2 == 0) ans = r;
else ans = l;
for (int i: s) {
if (s.find(i ^ 1) == s.end()) {
int cur = i ^ ans;
bool f = true;
for (int j : s)
f &= ((cur ^ j) >= l && (cur ^ j) <= r);
if (f) {
ans = cur;
break;
}
}
}
cout << ans * mul << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while (t--) solve();
return 0;
}
import sys
input = sys.stdin.readline
def solve(l: int, r: int, s: set):
if l % 2 == 0 and r % 2 == 1:
t = set()
for v in s: t.add(v >> 1)
return solve(l >> 1, r >> 1, t) << 1
else:
for v in s:
if (v ^ 1) not in s:
ok = True
ans = v
if l % 2 == 0: ans ^= r
else: ans ^= l
for x in s:
if (x ^ ans) < l or (x ^ ans) > r:
ok = False
break
if ok: return ans
t = int(input())
for _ in range (t):
l, r = map(int, input().split())
s = set(map(int, input().split()))
print(solve(l, r, s))
1658E - Годзё и игра на матрице
What if a player is forced to play in a cell where they get fewer points than the previous move?
Rephrase the problem, then solve it with dynamic programming.
Suppose that Marin places a token at $$$(a,b)$$$. If Gojou places a token at $$$(c,d)$$$ where $$$V_{c,d}<V_{a,b}$$$, then Gojou would not have any advantage as Marin can play at $$$(a,b)$$$ again. After a very huge number of turns, Marin will have more points than Gojou. Generally, if a player is forced to play in a cell where they get fewer points than the previous move, they would instantly lose.
Therefore, we can rephrase the problem as such:
This turns out to be a standard dynamic programming.
Let $$$dp[i][j]$$$ return $$$1$$$ if the player who places a token at $$$(i,j)$$$ wins.
Let $$$V_{a,b}=n^2$$$, then we have $$$dp[a][b]=1$$$ as a base case.
Then we will fill the values of $$$dp$$$ in decreasing values of $$$V_{i,j}$$$. $$$dp[i][j]=1$$$ if for all $$$(i',j')$$$ such that $$$|i-i'|+|j-j'| > k$$$, we have $$$dp[i'][j']=0$$$. Note that by taking the contrapositive, this is equivalent to for all $$$(i',j')$$$ such that $$$dp[i'][j']=1$$$, we have $$$|i-i'|+|j-j'| \leq k$$$.
Let us maintain a set $$$S$$$ that stores the pairs $$$(i',j')$$$ such that $$$dp[i'][j']=1$$$, then our operations are:
Notice that $$$|i-i'|+|j-j'| \leq k \Leftrightarrow \max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$$$.
Checking $$$\max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$$$ is very simple as we only need to store the minimum and maximum of all $$$(i+j)$$$ and $$$(i-j)$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
bool f[N][N];
int l, r, u, d, n, k;
vector<array<int, 5>> v;
bool check(int i, int j) {
return (abs(i - u) <= k && abs(i - d) <= k && abs(j - l) <= k && abs(j - r) <= k);
}
void solve(){
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
f[i][j] = false;
int x; cin >> x;
v.push_back({x, i, j, i + j, j - i});
}
}
sort(v.begin(), v.end(), greater<array<int, 5>>());
l = v[0][4], r = v[0][4], u = v[0][3], d = v[0][3];
for (array<int, 5> cell: v) {
if (check(cell[3], cell[4])) {
f[cell[1]][cell[2]] = true;
l = min(l, cell[4]);
r = max(r, cell[4]);
u = min(u, cell[3]);
d = max(d, cell[3]);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (f[i][j]) cout << 'M';
else cout << 'G';
}
cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
1658F - Дзюдзю и бинарная строка
Let $$$b$$$ be the number of black balls and $$$w$$$ be the number of white balls.
The answer will be impossible if $$$m$$$ is not a multiple of $$$\dfrac{b+w}{gcd(b, w)}$$$.
It is easy to show that the cuteness of $$$s$$$ is $$$\dfrac{b}{n}$$$.
What is the number of $$$\texttt{1}$$$ in the concatenated string needed so that the answer exists?
The cuteness of $$$s$$$ is $$$\dfrac{b}{n} = \dfrac{b}{b+w}$$$ by definition.
Now consider $$$t = s[l_1, r_1] + [l_2, r_2] + \dots + s[l_k, r_k]$$$, the cuteness of the concatenated string.
The cuteness of $$$t$$$ is $$$\dfrac{b}{b+w}$$$, so the number of $$$\texttt{1}$$$ needed is $$$k = \dfrac{m \cdot w}{b + w}$$$.
If $$$k$$$ is not an integer then there will be no answer, so $$$m$$$ must be a multiple of $$$\dfrac{b+w}{gcd(b, w)}$$$.
We don't need more than 2 parts, or to say $$$k \leq 2$$$ is needed in this problem.
Let $$$c_i =$$$ (the number of $$$\texttt{1}$$$ in $$$s[i \dots i + m - 1]$$$).
For convenient, from now let assume the array and string is wrapped around: $$$s[i] = s[i + n]$$$ and $$$c_i = c_{i+n}$$$.
We have $$$|c_i-c_{i+1}| \leq 1$$$ and there exists $$$c_i = y$$$ for all $$$y$$$ that $$$min(c_i) \leq y \leq max(c_i)$$$.
Let $$$L = min(c_i)$$$, $$$R = max(c_i)$$$ and we are doing with wrap around arrays for convenient.
We want to prove that for any $$$y$$$ that $$$L \leq y \leq R$$$ there will be some $$$c_i = y$$$.
Let $$$d_i = max(c_p, c_{p+1}, \dots, c_i)$$$ for $$$p$$$ is the minimal position that $$$c_p = L$$$.
Let $$$f_x$$$ is the first position $$$i$$$ starting $$$p$$$ that $$$d_i = x$$$, we have $$$d_{f_x} = c_{f_x}$$$
[1] Since $$$L \leq y \leq R$$$ and, we have $$$L = d_p \leq d_{p+1} \leq \dots \leq d_{p+n-1} = R$$$.
[2] Since $$$|c_{i+1} - c_i| \leq 1$$$ we can show that.
[3] Since $$$c_i \in \mathbb{N}$$$, we also have $$$d_i \in \mathbb{N}$$$
From [1], [2], [3], if there is $$$d_i = v > L$$$ then there will be $$$d_j = v - 1$$$ for some $$$j$$$ that $$$p + (v - L) \leq j < i$$$.
$$$\Leftrightarrow \forall v, min(d_i) \leq v \leq max(d_i) \rightarrow \exists d_{f_i} = v$$$
$$$\Leftrightarrow \exists d_{f_i} = y$$$
$$$\Leftrightarrow \exists c_{f_i} = y$$$
The answer will be impossible if $$$m$$$ is not a multiple of $$$\dfrac{b+w}{gcd(b, w)}$$$.
Otherwise, it is proved that $$$k \leq 2$$$ is needed.
Since we need to select a minimum $$$k$$$, let's first check if there is a solution with $$$k = 1$$$
If there exist such position $$$p$$$ that $$$1 \leq p \leq n - m + 1$$$ and $$$s[p, p + m - 1]$$$ have the same cuteness as $$$s[1, n]$$$ then we found an answer.
Otherwise there must be an answer with $$$k = 2$$$, and it is simple too
If there exist such position $$$p$$$ that $$$1 \leq p < m$$$ and $$$s[1, p] \cup s[n - (m - p) + 1, n]$$$ have the same cuteness as $$$s[1, n]$$$ then we found an answer.
Both can be done in linear $$$O(n)$$$ with the sliding window technique or prefixsum.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n, k; cin >> n >> k;
string s; cin >> s;
int one = count_if(s.begin(), s.end(), [](char c) { return c == '1'; });
if (1LL * one * k % n != 0) {
cout << "-1\n";
} else {
one = 1LL * one * k / n;
vector<int> suf(2 * n + 1);
for (int i = 1; i <= 2 * n; i++) {
suf[i] = suf[i - 1] + (s[(i - 1) % n] == '1');
if (i >= k && suf[i] == suf[i - k] + one) {
if (i <= n) {
cout << "1\n";
cout << i - k + 1 << " " << i << '\n';
} else {
cout << "2\n";
cout << 1 << " " << i - n << '\n';
cout << i - k + 1 << " " << n << '\n';
}
break;
}
}
}
}
}
Recently, I've learned a powerful data structure: Suffix Automaton
, and found out that it can solve lots of problems that can be solved with KMP/Z Function/Hash/...
in average time complexity $$$O(n)$$$.
Now I'm curious to know, what are the pros/cons of this data structure? And is there any problems that can't be solved with Suffix Automaton
but able to solve with others data structure? Thank you in advance!
(for people who doesn't know this data structure: Link 1, Link 2)
Name |
---|