Hope you all enjoyed the problemset! Editorials to problems H and I are not ready yet, we will add them as soon as possible. We apologize for weak pretests and easy problems for top participants.
By the way, solution authors did not necessarily prepare the problems. The solutions were chosen at random.
Idea: bthero Preparation: 244mhq
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
int tst;
cin >> tst;
while (tst--) {
int n;
cin >> n;
cout << (n + 1) / 10 << '\n';
}
}
Idea: Errichto Preparation: Will not be revealed for now because we care for his/their safety.
q = int(input())
for i in range(q):
s = input()
t = input()
n = len(s)
m = len(t)
ans = False
for i in range(n):
for j in range(0, n - i):
k = m - 1 - j
if i + j < k:
continue
l1 = i
r = i + j
l2 = r - k
if s[l1:r+1] + s[l2:r][::-1] == t:
ans = True
print('YES' if ans else 'NO')
Idea: Errichto Preparation: BledDest
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int ans = 9;
{
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < 10; ++i) {
if (i % 2 == 0) cnt0 += s[i] != '0';
else cnt1 += s[i] == '1';
if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);
if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);
}
}
{
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < 10; ++i) {
if (i % 2 == 0) cnt0 += s[i] == '1';
else cnt1 += s[i] != '0';
if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);
if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);
}
}
cout << ans + 1 << '\n';
}
}
Idea: Adel_SaadEddin, Zaher Preparation: Will not be revealed for now because we care for his/their safety.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 200200;
int n, m;
char s[N], t[N];
bool solve() {
scanf("%s %s", s, t);
n = strlen(s);
m = strlen(t);
if (n < m) return false;
int p = (n - m) & 1;
int q = 0;
int k = 0;
for (int i = p; i < n; i++) {
if (k == 1) {
k = 0;
continue;
}
if (q < m && s[i] == t[q]) {
q++;
} else {
k++;
}
}
return q == m;
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int T;
scanf("%d", &T);
while(T--) {
if (solve())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
Idea: bthero, 244mhq Preparation: BledDest
#include <bits/stdc++.h>
using namespace std;
int cycle_count(vector<int> q, int n)
{
for(int i = 0; i < n; i++)
q[i]--;
vector<int> used(n);
int ans = 0;
for(int i = 0; i < n; i++)
{
if(used[i] == 1) continue;
int j = i;
while(used[j] == 0)
{
used[j] = 1;
j = q[j];
}
ans++;
}
return ans;
}
bool check(int n, int m, int k, vector<int> p)
{
vector<int> q;
for(int i = k; i < n; i++)
q.push_back(p[i]);
for(int i = 0; i < k; i++)
q.push_back(p[i]);
return n - cycle_count(q, n) <= m;
}
void solve()
{
int n, m;
scanf("%d %d", &n, &m);
vector<int> p(n);
for(int i = 0; i < n; i++)
scanf("%d", &p[i]);
vector<int> cnt(n);
for(int i = 0; i < n; i++)
{
int offset = i + 1 - p[i];
if(offset < 0)
offset += n;
cnt[offset]++;
}
vector<int> ans;
for(int i = 0; i < n; i++)
if(cnt[i] + 2 * m >= n && check(n, m, i, p))
ans.push_back(i);
printf("%d", ans.size());
for(auto x : ans) printf(" %d", x);
puts("");
}
int main()
{
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
{
solve();
}
}
Idea: 244mhq, Errichto Preparation: bthero
// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<int N> struct Fenw {
ll t[N + 1];
Fenw() {
fill(t + 1, t + N + 1, 0ll);
}
void update(int p, ll x) {
for (; p <= N; p |= (p + 1)) {
t[p] += x;
}
}
ll get(int p) {
ll ret = 0;
for (; p > 0; --p) {
ret += t[p];
p &= (p + 1);
}
return ret;
}
ll get(int l, int r) {
return get(r) - get(l - 1);
}
};
const int M = (int)3e5;
void solve() {
int n;
cin >> n;
Fenw<M> A, B;
ll pref = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
ans += x * (i - 1ll);
ans += A.get(x);
ans += pref;
pref += x;
for (int j = x; j <= M; j += x) {
int l = j, r = min(M, j + x - 1);
ans -= B.get(l, r) * j;
A.update(l, -x);
}
B.update(x, 1);
cout << ans << " \n"[i == n];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
for (int i = 1; i <= tt; ++i) {
solve();
}
return 0;
}
Idea: Adel_SaadEddin, Zaher, Errichto Preparation: Errichto
// gcd, AC, O((N+Q) * log^2), by Errichto
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
struct DSU {
vector<int> parent;
DSU(int m) {
parent.resize(m + 1);
for(int i = 0; i <= m; ++i) {
parent[i] = i;
}
}
int find(int a) {
if(a == parent[a]) {
return a;
}
return parent[a] = find(parent[a]);
}
void uni(int a, int b) {
parent[find(a)] = find(b);
}
};
int main() {
// 1) read input
int n, q;
scanf("%d%d", &n, &q);
vector<int> a(n);
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
int m = *max_element(a.begin(), a.end());
// 2) prime sieve
vector<vector<int>> prime_divisors(m + 2);
for(int p = 2; p <= m + 1; ++p) {
if(prime_divisors[p].empty()) {
for(int j = p; j <= m + 1; j += p) {
prime_divisors[j].push_back(p);
}
}
}
// 3) DSU, find initial connected components
DSU dsu(m + 2);
for(int x : a) {
for(int p : prime_divisors[x]) {
dsu.uni(x, p);
}
}
// 4) DSU, find edges of cost 1
set<pair<int,int>> edges;
for(int x : a) {
vector<int> nodes = prime_divisors[x+1];
nodes.push_back(x);
for(int& node : nodes) {
node = dsu.find(node);
}
for(int i = 0; i < (int) nodes.size(); ++i) {
for(int j = i + 1; j < (int) nodes.size(); ++j) {
int one = nodes[i];
int two = nodes[j];
if(one != two) {
if(one > two) {
swap(one, two);
}
edges.insert({one, two});
}
}
}
}
debug() << imie(edges);
cerr << imie(edges.size()) << endl;
// 5) answer queries
while(q--) {
int s, t;
scanf("%d%d", &s, &t);
--s;
--t;
s = dsu.find(a[s]);
t = dsu.find(a[t]);
if(s == t) {
puts("0");
}
else if(edges.count({min(s, t), max(s, t)})) {
puts("1");
}
else {
puts("2");
}
}
}
Idea: 244mhq Preparation: BledDest, mnaeraxr, 244mhq
#include<bits/stdc++.h>
using namespace std;
const int INF = int(1e9);
const int K = 20;
struct node
{
int max_val, min_val, ans, len;
node(const node& left, const node& right)
{
len = left.len + right.len;
max_val = max(left.max_val, right.max_val + left.len);
min_val = min(left.min_val, right.min_val + left.len);
ans = min(min(left.ans, right.ans), min(INF, right.min_val - left.max_val + left.len));
}
node(int x)
{
ans = INF;
len = 1;
if(x == 1)
max_val = min_val = 0;
else
{
max_val = -INF;
min_val = INF;
}
}
node() {};
};
int cnt[1 << K];
vector<node> tree[2 << K];
void build(int v, int l, int r)
{
tree[v].resize(r - l);
if(l == r - 1)
{
tree[v][0] = node(cnt[l]);
}
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
for(int i = 0; i < m - l; i++)
{
tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]);
}
}
}
int main()
{
int n, k;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
cnt[x]++;
}
int m = 1 << k;
build(0, 0, m);
for(int i = 0; i < m; i++)
printf("%d ", tree[0][i].ans);
puts("");
}
Idea: bthero, 244mhq, BledDest Preparation: BledDest, 244mhq
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define sz(a) ((int)((a).size()))
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
template<const int &MOD>
struct _m_int {
int val;
_m_int(int64_t v = 0) {
if (v < 0) v = v % MOD + MOD;
if (v >= MOD) v %= MOD;
val = int(v);
}
_m_int(uint64_t v) {
if (v >= MOD) v %= MOD;
val = int(v);
}
_m_int(int v) : _m_int(int64_t(v)) {}
_m_int(unsigned v) : _m_int(uint64_t(v)) {}
static int inv_mod(int a, int m = MOD) {
int g = m, r = a, x = 0, y = 1;
while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
explicit operator int() const { return val; }
explicit operator unsigned() const { return val; }
explicit operator int64_t() const { return val; }
explicit operator uint64_t() const { return val; }
explicit operator double() const { return val; }
explicit operator long double() const { return val; }
_m_int& operator+=(const _m_int &other) {
val -= MOD - other.val;
if (val < 0) val += MOD;
return *this;
}
_m_int& operator-=(const _m_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
return unsigned(x % m);
#endif
// Optimized mod for Codeforces 32-bit machines.
// x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;
}
_m_int& operator*=(const _m_int &other) {
val = fast_mod(uint64_t(val) * other.val);
return *this;
}
_m_int& operator/=(const _m_int &other) {
return *this *= other.inv();
}
friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
_m_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
_m_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
_m_int operator++(int) { _m_int before = *this; ++*this; return before; }
_m_int operator--(int) { _m_int before = *this; --*this; return before; }
_m_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
_m_int inv() const {
return inv_mod(val);
}
_m_int pow(int64_t p) const {
if (p < 0)
return inv().pow(-p);
_m_int a = *this, result = 1;
while (p > 0) {
if (p & 1)
result *= a;
a *= a;
p >>= 1;
}
return result;
}
friend ostream& operator<<(ostream &os, const _m_int &m) {
return os << m.val;
}
};
extern const int MOD = 998244353;
using Mint = _m_int<MOD>;
const int LOGN = 19;
const int N = (1 << LOGN);
const int T = 2;
Mint g = 3;
vector<Mint> w[LOGN];
vector<int> rv[LOGN];
void precalc() {
Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
forn(st, LOGN - 1) {
w[st].assign(1 << st, 1);
Mint bw = wb.pow(1 << (LOGN - st - 1));
Mint cw = 1;
forn(k, 1 << st) {
w[st][k] = cw;
cw *= bw;
}
}
forn(st, LOGN) {
rv[st].assign(1 << st, 0);
if (st == 0) {
rv[st][0] = 0;
continue;
}
int h = (1 << (st - 1));
forn(k, 1 << st)
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
}
}
void ntt(vector<Mint> &a, bool inv) {
int n = sz(a);
int ln = __builtin_ctz(n);
forn(i, n) {
int ni = rv[ln][i];
if (i < ni) swap(a[i], a[ni]);
}
forn(st, ln) {
int len = 1 << st;
for (int k = 0; k < n; k += (len << 1)) {
fore(pos, k, k + len){
Mint l = a[pos];
Mint r = a[pos + len] * w[st][pos - k];
a[pos] = l + r;
a[pos + len] = l - r;
}
}
}
if (inv) {
Mint rn = Mint(n).inv();
forn(i, n) a[i] *= rn;
reverse(a.begin() + 1, a.end());
}
}
vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
a.resize(cnt);
b.resize(cnt);
ntt(a, false);
ntt(b, false);
vector<Mint> c(cnt);
forn(i, cnt) c[i] = a[i] * b[i];
ntt(c, true);
while(c.size() > 1 && c.back() == 0)
c.pop_back();
return c;
}
struct dp
{
vector<Mint> val[T][T];
bool is_unit;
dp() {};
dp(int len)
{
is_unit = len == 1;
for(int j = 0; j < T; j++)
for(int k = 0; k < T; k++)
val[j][k] = {0};
if(len == 1)
val[0][0][0] = 1;
else
val[1][1][0] = 2;
}
dp(const dp& a, const dp& b)
{
is_unit = false;
for(int l1 = 0; l1 < T; l1++)
for(int r1 = 0; r1 < T; r1++)
for(int l2 = 0; l2 < T; l2++)
for(int r2 = 0; r2 < T; r2++)
{
vector<Mint> cur = mul(a.val[l1][r1], b.val[l2][r2]);
if(val[l1][r2].size() < cur.size())
val[l1][r2].resize(cur.size());
for(int i = 0; i < cur.size(); i++)
val[l1][r2][i] += cur[i];
Mint merge_coeff = 2;
if(r1 == 1)
merge_coeff /= 2;
if(l2 == 1)
merge_coeff /= 2;
cur.insert(cur.begin(), 0);
for(int i = 0; i < cur.size(); i++)
cur[i] *= merge_coeff;
int L1 = l1;
int R2 = r2;
if(a.is_unit)
L1 = 1;
if(b.is_unit)
R2 = 1;
if(val[L1][R2].size() < cur.size())
val[L1][R2].resize(cur.size());
for(int i = 0; i < cur.size(); i++)
{
val[L1][R2][i] += cur[i];
}
}
}
};
ostream& operator<<(ostream& out, const dp& a)
{
for(int i = 0; i < T; i++)
for(int j = 0; j < T; j++)
{
out << "[" << i << "][" << j << "]";
for(auto x : a.val[i][j])
out << " " << x;
out << endl;
}
return out;
}
int a[N];
int len[N];
Mint fact[N];
int n;
int s;
dp build(int l, int r)
{
if(l == r - 1)
{
dp res(len[l]);
//cerr << l << " " << r << endl;
//cerr << res;
return res;
}
else
{
int m = (l + r) / 2;
dp res(build(l, m), build(m, r));
//cerr << l << " " << r << endl;
//cerr << res;
return res;
}
}
int main()
{
precalc();
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
int cur = 0;
while(cur != n)
{
if(cur + a[cur] > n)
{
cout << 0 << endl;
return 0;
}
for(int l = cur; l < cur + a[cur]; l++)
if(a[l] != a[cur])
{
cout << 0 << endl;
return 0;
}
len[s++] = a[cur];
cur += a[cur];
}
fact[0] = 1;
for(int i = 1; i <= s; i++)
fact[i] = i * fact[i - 1];
dp res = build(0, s);
Mint ans = 0;
for(int i = 0; i < s; i++)
for(int j = 0; j < T; j++)
for(int k = 0; k < T; k++)
if(res.val[j][k].size() > i)
ans += fact[s - i] * res.val[j][k][i] * (i % 2 == 0 ? 1 : MOD - 1);
cout << ans << endl;
}