Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon) 1
#include <bits/stdc++.h>
using namespace std;
int main() {
auto ok = [](string s) {
for (int i = 1; i < (int)s.size(); ++i)
if (s[i - 1] == s[i]) return false;
return true;
};
int t;
cin >> t;
while (t--) {
int n, m;
string s, t;
cin >> n >> m >> s >> t;
bool f = false;
for (int x = 0; x < 2; ++x) {
string cs = s, ct = t;
for (int i = 0; i < n; ++i) {
f |= ok(cs) && ok(ct);
ct.push_back(cs.back());
cs.pop_back();
}
swap(n, m);
swap(s, t);
}
cout << (f ? "YES\n" : "NO\n");
}
}
Solution (Neon) 2
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
string s, t;
cin >> n >> m >> s >> t;
reverse(t.begin(), t.end());
s += t;
int cnt = 0;
for (int i = 1; i < n + m; ++i) cnt += s[i - 1] == s[i];
cout << (cnt <= 1 ? "YES\n" : "NO\n");
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int L = 0, R = 55;
while (n--) {
int l, r;
cin >> l >> r;
if (l <= k && k <= r)
L = max(L, l), R = min(R, r);
}
cout << (L == R ? "YES\n" : "NO\n");
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<li> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
vector<li> sum(n + 1);
for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + b[i];
vector<li> cnt(n + 1), add(n + 1);
for (int i = 0; i < n; ++i) {
int j = upper_bound(sum.begin(), sum.end(), a[i] + sum[i]) - sum.begin() - 1;
cnt[i] += 1;
cnt[j] -= 1;
add[j] += a[i] - sum[j] + sum[i];
}
for (int i = 0; i < n; ++i) {
cout << cnt[i] * b[i] + add[i] << ' ';
cnt[i + 1] += cnt[i];
}
cout << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
return ((x + y) % MOD + MOD) % MOD;
}
int mul(int x, int y)
{
return x * 1ll * y % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
int main()
{
int n;
cin >> n;
int ans = 1;
for(int i = 1; i <= n / 6; i++)
ans = mul(ans, divide(i + n / 6, i));
for(int i = 0; i < n / 3; i++)
{
vector<int> a(3);
for(int j = 0; j < 3; j++)
cin >> a[j];
int mn = *min_element(a.begin(), a.end());
int cnt_min = count(a.begin(), a.end(), mn);
ans = mul(ans, cnt_min);
}
cout << ans << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (adedalic)
import java.util.*
fun main() {
repeat(readln().toInt()) {
val n = readln().toInt()
var h = readln().split(' ').map { it.toInt() }
val d = Array(2) { LongArray(n) { 0 } }
for (tp in 0..1) {
val s = Stack<Pair<Int, Int>>()
for (i in h.indices) {
while (s.isNotEmpty() && s.peek().first > h[i] - i)
s.pop()
var j = maxOf(-1, i - h[i])
if (s.isNotEmpty())
j = maxOf(j, s.peek().second)
val len = (i - j).toLong()
d[tp][i] = len * h[i] - len * (len - 1) / 2
if (j >= 0 && len < h[i])
d[tp][i] += d[tp][j]
s.push(Pair(h[i] - i, i))
}
h = h.reversed()
}
d[1] = d[1].reversedArray()
var ans = 1e18.toLong()
val sum = h.fold(0L) { total, it -> total + it }
for (i in h.indices) {
val cur = sum - d[0][i] - d[1][i] + 2 * h[i]
ans = minOf(ans, cur)
}
println(ans)
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
vector<vector<int>> g;
vector<int> req;
vector<char> used;
vector<int> d;
bool dfs(int v, int p = -1){
d[v] = 0;
for (int u : g[v]) if (u != p){
if (!dfs(u, v)) return false;
if (!used[u]) d[v] = max(d[v], d[u] + 1);
}
if (req[v] == 0 || d[v] >= req[v]) return true;
if (p == -1 || used[p]) return false;
used[p] = true;
req[p] = req[v] - 1;
return true;
}
int main(){
int t;
scanf("%d", &t);
while (t--){
int n;
scanf("%d", &n);
g.assign(n, {});
d.resize(n);
forn(i, n - 1){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
int k;
scanf("%d", &k);
vector<int> a(k);
forn(i, k){
scanf("%d", &a[i]);
--a[i];
}
int l = 1, r = n;
int res = 0;
while (l <= r){
int m = (l + r) / 2;
used.assign(n, 0);
req.assign(n, 0);
forn(i, k){
used[a[i]] = true;
req[a[i]] = m / k + (i < m % k);
}
if (dfs(0)){
res = m;
l = m + 1;
}
else{
r = m - 1;
}
}
printf("%d\n", res);
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
typedef unsigned long long uli;
int main(){
int t;
scanf("%d", &t);
while (t--){
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<vector<int>> g(n);
forn(i, m){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
vector<char> rem(n);
vector<int> d(n);
forn(i, n) d[i] = g[i].size();
queue<int> q;
forn(i, n) if (a[i] == d[i]) q.push(i);
vector<pair<int, int>> ord;
while (!q.empty()){
int v = q.front();
q.pop();
rem[v] = true;
for (int u : g[v]) if (!rem[u]){
--d[u];
ord.push_back({v, u});
if (d[u] == a[u])
q.push(u);
}
}
reverse(ord.begin(), ord.end());
vector<uli> mask(n);
long long ans = n * 1ll * (n + 1) / 2;
for (int l = 0; l < n; l += 64){
int r = min(n, l + 64);
for (int i = l; i < r; ++i)
mask[i] = 1ull << (i - l);
for (const pair<int, int> &it : ord)
mask[it.first] |= mask[it.second];
forn(i, n){
ans -= __builtin_popcountll(mask[i]);
mask[i] = 0;
}
}
printf("%lld\n", ans);
}
}