Author: FairyWinx
Preparation: FairyWinx
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
if (s == "^") {
cout << 1 << '\n';
continue;
}
int ans = 0;
if (s[0] == '_')
++ans;
if (s.back() == '_')
++ans;
for (int i = 0; i < (int) s.size() - 1; ++i) {
if (s[i] == '_' && s[i + 1] == '_')
++ans;
}
cout << ans << '\n';
}
}
1820B - JoJo's Incredible Adventures
Author: golikovnik
Preparation: teraqqq
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
string s; cin >> s; s += s;
int k = 0, z = 0;
for (char c : s) {
z = c == '1' ? z+1 : 0;
k = max(k, z);
}
const int n = s.size() / 2;
if (k > n) {
cout << (ll)n*n << '\n';
} else {
const ll side_a = (k+1)/2;
const ll side_b = (k+2)/2;
cout << side_a * side_b << '\n';
}
}
}
Author: TeaTime
Preparation: golikovnik
Editorial
Tutorial is loading...
Solution
// Nikita Golikov, 2023
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#ifdef GOLIKOV
#define debug(x) cerr << (#x) << ":\t" << (x) << endl
#else
#define debug(x) 238;
#endif
template <class A, class B>
bool smin(A& x, B&& y) {
if (y < x) {
x = y;
return true;
}
return false;
}
template <class A, class B>
bool smax(A& x, B&& y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <class T>
int calcMex(vector<T> v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int n = int(v.size());
for (int i = 0; i < n; ++i) if (v[i] != i) return i;
return n;
}
bool solveTest() {
int n; cin >> n;
vector<int> a(n);
map<int, int> leftOcc, rightOcc;
for (int i = 0; i < n; ++i) {
cin >> a[i];
rightOcc[a[i]] = i;
if (!leftOcc.count(a[i])) leftOcc[a[i]] = i;
}
int mex = calcMex(a);
if (leftOcc.count(mex + 1)) {
int L = leftOcc[mex + 1], R = rightOcc[mex + 1];
for (int i = L; i <= R; ++i) {
a[i] = mex;
}
int mx = calcMex(a);
assert(mx <= mex + 1);
return mx == mex + 1;
}
for (int i = 0; i < n; ++i) {
assert(a[i] != mex);
if (a[i] > mex || (leftOcc[a[i]] != rightOcc[a[i]])) {
return true;
}
}
return false;
}
int main() {
#ifdef GOLIKOV
assert(freopen("in", "rt", stdin));
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
cout << (solveTest() ? "Yes" : "No") << '\n';
}
#ifdef GOLIKOV
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Author: Tikhon228
Preparation: Kon567889
Editorial
Tutorial is loading...
Solution
//#pragma GCC target("trapv")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <iostream>
#include <list>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
const ll INF = 1e9 * 1e9 + 100, SZ = 1100;
ll n;
vector<pair<ll, ll>> vec;
map<ll, pair<ll, ll>> blocks;
pair<ll, ll> solve() {
set<pair<ll, ll>> widest, longest;
for (size_t i = 0; i < vec.size(); i++) {
widest.insert({ vec[i].first, i });
longest.insert({ vec[i].second, i });
blocks[i] = vec[i];
}
pair<ll, ll> ans = { -1, -1 };
bool mode = 0;
ll prevw = INF, prevh = INF, prv = -1;
bool cringe = 0;
while (widest.size() != 0) {
if (mode == 0) {
ll cur = (*widest.rbegin()).first, sum = 0;
if (ans.second == -1) ans.second = cur;
prv = blocks[(*widest.rbegin()).second].second;
while (widest.size() > 0 && (*widest.rbegin()).first == cur) {
auto it = (--widest.end());
longest.erase({blocks[it->second].second, it->second });
sum += blocks[it->second].second;
widest.erase(it);
}
if (!cringe) ans.first = sum;
prv = sum;
if (prevw == INF) {
prevh = cur;
} else {
prevw -= sum;
if (prevh != cur) return { -1, -1 };
}
} else {
ll cur = (*longest.rbegin()).first, sum = 0;
if (!cringe) {
ans.first = cur + prv;
cringe = 1;
}
while (longest.size() > 0 && (*longest.rbegin()).first == cur) {
auto it = (--longest.end());
widest.erase({ blocks[it->second].first, it->second });
sum += blocks[it->second].first;
longest.erase(it);
}
if (prevw == INF) {
prevw = cur;
prevh -= sum;
if (prevw != cur) return { -1, -1 };
} else {
prevh -= sum;
if (prevw != cur) return { -1, -1 };
}
}
mode ^= 1;
}
if (prevh == 0 || prevw == 0 || prevh == INF || prevw == INF) {
return ans;
} else {
return { -1, -1 };
}
}
signed main() {
fastInp;
ll t;
cin >> t;
while (t--) {
vec.clear();
blocks.clear();
cin >> n;
vec.resize(n);
for (auto& c : vec) cin >> c.first >> c.second;
vector<pair<ll, ll>> ans;
ans.push_back(solve());
swap(ans.back().first, ans.back().second);
if (ans.back().first == -1) ans.pop_back();
for (auto& c : vec) swap(c.first, c.second);
ans.push_back(solve());
if (ans.back().first == -1) ans.pop_back();
if (ans.size() == 2 && ans[0] == ans[1]) {
ans.pop_back();
}
cout << ans.size() << "\n";
for (auto c : ans) cout << c.first << " " << c.second << "\n";
}
return 0;
}
1819C - The Fox and the Complete Tree Traversal
Author: golikovnik
Preparation: DishonoredRighteous
Editorial
Tutorial is loading...
Solution
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <stdio.h>
#include <bits/stdc++.h>
#ifdef PERVEEVM_LOCAL
#define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
#define debug(x) 238
#endif
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"
using ll = long long;
using ld = long double;
#ifdef PERVEEVM_LOCAL
std::mt19937 rnd(238);
#else
std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
template<typename T>
bool smin(T& a, const T& b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool smax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 200100;
std::vector<int> g[N];
int d[N], par[N];
bool onDiameter[N];
void dfs(int v, int p, int depth) {
d[v] = depth;
par[v] = p;
for (auto to : g[v]) {
if (to != p) {
dfs(to, v, depth + 1);
}
}
}
void run() {
int n;
scanf("%d", &n);
for (int i = 0; i < n - 1; ++i) {
int from, to;
scanf("%d%d", &from, &to);
g[from - 1].push_back(to - 1);
g[to - 1].push_back(from - 1);
}
dfs(0, 0, 0);
int v1 = 0;
for (int i = 0; i < n; ++i) {
if (d[i] > d[v1]) {
v1 = i;
}
}
dfs(v1, v1, 0);
int v2 = v1;
for (int i = 0; i < n; ++i) {
if (d[i] > d[v2]) {
v2 = i;
}
}
std::vector<int> diameter;
for (int v = v2; v != v1; v = par[v]) {
onDiameter[v] = true;
diameter.push_back(v);
}
onDiameter[v1] = true;
diameter.push_back(v1);
std::reverse(diameter.begin(), diameter.end());
for (int i = 0; i < n; ++i) {
if (onDiameter[i]) {
continue;
}
if (!onDiameter[par[i]]) {
printf("No\n");
return;
}
}
printf("Yes\n");
std::vector<int> ans;
for (int i = 0; i < (int)diameter.size(); i += 2) {
ans.push_back(diameter[i]);
if (i + 1 != (int)diameter.size()) {
for (auto to : g[diameter[i + 1]]) {
if (!onDiameter[to]) {
ans.push_back(to);
}
}
}
}
if (diameter.size() % 2 == 0) {
for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {
ans.push_back(diameter[i]);
if (i - 1 >= 0) {
for (auto to : g[diameter[i - 1]]) {
if (!onDiameter[to]) {
ans.push_back(to);
}
}
}
}
} else {
for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {
ans.push_back(diameter[i - 1]);
if (i - 2 >= 0) {
for (auto to : g[diameter[i - 2]]) {
if (!onDiameter[to]) {
ans.push_back(to);
}
}
}
}
}
assert((int)ans.size() == n);
for (auto i : ans) {
printf("%d ", i + 1);
}
printf("\n");
}
int main(void) {
// freopen(NAME".in", "r", stdin);
// freopen(NAME".out", "w", stdout);
#ifdef PERVEEVM_LOCAL
auto start = std::chrono::high_resolution_clock::now();
#endif
run();
#ifdef PERVEEVM_LOCAL
auto end = std::chrono::high_resolution_clock::now();
std::cerr << "Execution time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms" << std::endl;
#endif
return 0;
}
Author: Um_nik
Preparation: dshindov
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#include <exception>
using namespace std;
using ll = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> apples(n);
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
for (int j = 0; j < k; ++j) {
int x;
cin >> x;
apples[i].push_back(x);
}
}
// vector<int> last(m + 1, -1);
unordered_map<int, int> last;
auto get_last = [&](int i) {
if (!last.count(i)) {
return -1;
} else {
return last[i];
}
};
vector<char> can_zero(n + 1, false);
vector<int> prev(n + 1, 0);
can_zero[0] = true;
int oops = -1;
for (int i = 0; i < n; ++i) {
if (apples[i].empty()) {
can_zero[i + 1] = true;
last[0] = i;
} else {
int nearest_pair = get_last(0);
int new_oops = oops;
for (int x : apples[i]) {
nearest_pair = max(nearest_pair, get_last(x));
new_oops = max(new_oops, get_last(x));
last[x] = i;
}
if (nearest_pair != -1) {
int nearest_zero = prev[nearest_pair];
if (oops < nearest_zero) {
can_zero[i + 1] = true;
}
}
oops = new_oops;
}
if (can_zero[i + 1]) {
prev[i + 1] = i + 1;
} else {
prev[i + 1] = prev[i];
}
}
// vector<char> used(m + 1, false);
unordered_set<int> used;
vector<int> max_cnt(n + 1, 0);
int current_cnt = 0;
for (int i = n - 1; i >= 0; --i) {
bool fail = false;
if (apples[i].empty()) {
used.insert(0);
}
for (int x : apples[i]) {
if (used.count(x)) {
fail = true;
break;
}
used.insert(x);
++current_cnt;
}
if (fail) {
break;
}
if (used.count(0)) {
max_cnt[i] = m;
} else {
max_cnt[i] = current_cnt;
}
}
int ans = 0;
for (int i = 0; i <= n; ++i) {
if (can_zero[i]) {
ans = max(ans, max_cnt[i]);
}
}
cout << ans << '\n';
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--) solve();
}
Author: Tikhon228
Preparation: grphil
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
mt19937 rnd;
struct solve {
vector<pair<int, int>> r;
vector<vector<pair<int, int>>> s;
vector<int> ans;
int n, m;
static constexpr int rep = 45;
int dfs(int a, int p, int b) {
for (auto i : s[a]) {
if (i.x == b) {
return i.y;
}
if (i.x == p) {
continue;
}
int x = dfs(i.x, a, b);
if (x != -1) {
return x;
}
}
return -1;
}
solve() {
cin >> n >> m;
r.resize(m);
for (int i = 0; i < m; i++) {
cin >> r[i].x >> r[i].y;
r[i].x--;
r[i].y--;
}
s.resize(n);
ans.resize(m, -1);
int cnt = 0;
for (int i = 0; i < m; i++) {
rem(i);
for (int j = 0; j < rep; j++) {
if (!ask_end(i)) {
ans[i] = 1;
break;
}
}
if (ans[i] == 1) {
add(i);
cnt++;
s[r[i].x].emplace_back(r[i].y, i);
s[r[i].y].emplace_back(r[i].x, i);
}
}
assert(cnt == n - 1);
for (int i = 0; i < m; i++) {
if (ans[i] != -1) continue;
ans[i] = 1;
int c = dfs(r[i].x, -1, r[i].y);
rem(c);
add(i);
for (int j = 0; j < rep; j++) {
if (!ask_end(i)) {
ans[i] = 0;
break;
}
}
rem(i);
add(c);
}
cout << "!";
for (int i = 0; i < m; i++) {
cout << ' ' << ans[i];
}
cout << endl;
int x;
cin >> x;
if (x != 1) {
exit(1);
}
}
void rem(int x) {
cout << "- " << x + 1 << endl;
}
void add(int x) {
cout << "+ " << x + 1 << endl;
}
bool ask(int a) {
cout << "? " << a + 1 << endl;
// cerr << "? " << a + 1 << endl;
int x;
cin >> x;
return x == 1;
}
bool ask_end(int i) {
// cerr << "ask_end " << i << endl;
int a = r[i].x;
if (rnd() % 2) {
a = r[i].y;
}
return ask(a);
}
};
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
solve();
}
}
1819F - Willy-nilly, Crack, Into Release!
Author: teraqqq
Preparation: teraqqq
Editorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using ll = long long;
const int Q = 1e5;
const int N = 20;
const int V = N*Q;
const ll LINF = 1e18;
struct MinMaxValue {
ll min_value;
ll max_value;
MinMaxValue operator * (const MinMaxValue& x) const {
if (x.max_value < 0 || max_value < 0) {
return MinMaxValue { 0, -1 };
}
return MinMaxValue {
.min_value = x.min_value + min_value,
.max_value = x.max_value + max_value
};
}
MinMaxValue operator + (const MinMaxValue& x) const {
if (x.max_value == -1) return *this;
if (max_value == -1) return x;
return MinMaxValue {
.min_value = min(x.min_value, min_value),
.max_value = max(x.max_value, max_value)
};
}
MinMaxValue& operator += (const MinMaxValue& x) {
return *this = *this + x;
}
void Reset() {
min_value = 0;
max_value = -1;
}
};
struct {
MinMaxValue dig, ver, hor;
int cnt;
int go[4];
} nd[V];
int vc = 0;
MinMaxValue dig[N+1], ver[N+1], hor[N+1];
std::set<ll> words;
int NewVertex(int h) {
int* go = nd[vc].go;
go[0] = go[1] = go[2] = go[3] = -1;
nd[vc].dig = dig[h];
nd[vc].hor = hor[h];
nd[vc].ver = ver[h];
nd[vc].cnt = 0;
return vc++;
}
tuple<const MinMaxValue&, const MinMaxValue&, const MinMaxValue&, int> GetState(int v, int h) {
return v == -1 ? make_tuple(cref(dig[h]), cref(ver[h]), cref(hor[h]), 0)
: make_tuple(cref(nd[v].dig), cref(nd[v].ver), cref(nd[v].hor), nd[v].cnt);
}
void Calculate(int v, int h, int corner) {
auto [dig0, ver0, hor0, cnt0] = GetState(nd[v].go[corner^0], h-1);
auto [dig1, ver1, hor1, cnt1] = GetState(nd[v].go[corner^1], h-1);
auto [dig2, ver2, hor2, cnt2] = GetState(nd[v].go[corner^2], h-1);
auto [dig3, ver3, hor3, cnt3] = GetState(nd[v].go[corner^3], h-1);
nd[v].cnt = cnt0 + cnt1 + cnt2 + cnt3;
nd[v].dig.Reset();
if (cnt0 == 0) nd[v].dig += hor2 * dig3 * ver1;
if (cnt3 == 0) nd[v].dig += ver2 * dig0 * hor1;
nd[v].hor = ver0 * dig2 * dig3 * ver1;
if (cnt2 + cnt3 == 0) nd[v].hor += hor0 * hor1;
nd[v].ver = hor0 * dig1 * dig3 * hor2;
if (cnt1 + cnt3 == 0) nd[v].ver += ver0 * ver2;
}
void UpdateCount(int v, int h, int corner, ll msk, ll msk_save) {
if (h == 0) {
if (nd[v].cnt == 0) {
words.insert(msk_save);
} else {
words.erase(msk_save);
}
nd[v].cnt ^= 1;
} else {
UpdateCount(nd[v].go[msk & 3], h-1, msk & 3, msk >> 2, msk_save);
Calculate(v, h, corner);
}
}
bool near_symbols[256][256];
MinMaxValue GetAnswer(int h) {
int v = 0;
if (nd[v].cnt == 0) {
return MinMaxValue { .min_value = 2, .max_value = 4 * dig[h-1].max_value };
}
MinMaxValue res; res.Reset();
bool cycle_len2 = false;
if (nd[v].cnt <= 1) cycle_len2 = true;
if (nd[v].cnt == 2) {
string s, t;
for (ll msk = *words.begin(); s.size() < h; msk >>= 2) s.push_back("abdc"[msk & 3]);
for (ll msk = *next(words.begin()); t.size() < h; msk >>= 2) t.push_back("abdc"[msk & 3]);
auto flag = near_symbols[s.back()][t.back()];
if (s.substr(0, h-1) == t.substr(0, h-1) && flag) {
cycle_len2 = true;
}
int s_suf = 0, t_suf = 0;
while (s_suf < h && s[h - s_suf - 1] == s.back()) ++s_suf;
while (t_suf < h && t[h - t_suf - 1] == t.back()) ++t_suf;
if (s_suf == t_suf && s_suf < h && flag && s.substr(0, h-s_suf-1) == t.substr(0, h-t_suf-1)
&& s.back() == t[h - s_suf - 1]
&& t.back() == s[h - t_suf - 1]) cycle_len2 = true;
}
if (cycle_len2) {
res.min_value = 2;
res.max_value = 2;
}
while (h != 0) {
const int v0 = nd[v].go[0], v1 = nd[v].go[1], v2 = nd[v].go[2], v3 = nd[v].go[3];
const auto& dig0 = get<0>(GetState(v0, h-1));
const auto& dig1 = get<0>(GetState(v1, h-1));
const auto& dig2 = get<0>(GetState(v2, h-1));
const auto& dig3 = get<0>(GetState(v3, h-1));
if(dig0.max_value > 0 && dig1.max_value > 0 && dig2.max_value > 0 && dig3.max_value > 0) {
res += dig0 * dig1 * dig2 * dig3;
}
--h;
if (v0 != -1 && nd[v0].cnt == nd[v].cnt) { v = v0; continue; }
if (v1 != -1 && nd[v1].cnt == nd[v].cnt) { v = v1; continue; }
if (v2 != -1 && nd[v2].cnt == nd[v].cnt) { v = v2; continue; }
if (v3 != -1 && nd[v3].cnt == nd[v].cnt) { v = v3; continue; }
break;
}
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
vector<ll> v(q);
for (int i = 0; i < 4; ++i) {
int j = (i + 1) % 4;
near_symbols['a' + i]['a' + j] = true;
near_symbols['a' + j]['a' + i] = true;
}
dig[0] = ver[0] = hor[0] = { 1, 1 };
for (int i = 1; i <= n; ++i) {
dig[i] = hor[i-1] * dig[i-1] * ver[i-1];
hor[i] = ver[i] = hor[i-1] * hor[i-1] + ver[i-1] * ver[i-1] * dig[i-1] * dig[i-1];
}
int m_root = NewVertex(n); // make_root
assert(m_root == 0);
for (int i = 0; i < q; ++i) {
string s; cin >> s;
for (int j = 0; j < n; ++j) {
v[i] += (s[j] == 'b' || s[j] == 'c' ? 1ll : 0) << (2*j);
v[i] += (s[j] == 'c' || s[j] == 'd' ? 2ll : 0) << (2*j);
}
int w = 0;
for (int j = 0; j < n; ++j) {
int& next = nd[w].go[(v[i] >> (2*j)) & 3];
if (next == -1) next = NewVertex(n-j-1);
w = next;
}
}
for (ll msk : v) {
UpdateCount(0, n, 0, msk, msk);
auto [a, b] = GetAnswer(n);
if (a > b) {
cout << -1 << '\n';
} else {
cout << a << " " << b << '\n';
}
}
}