Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
s = input()
print("YES" if list(s) == sorted(s) else "NO")
1976B - Increase/Decrease/Copy
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<li> a(n), b(n + 1);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
li sum = 0, ext = 1e18;
for (int i = 0; i < n; ++i) {
sum += abs(a[i] - b[i]);
ext = min(ext, abs(a[i] - b[n]));
ext = min(ext, abs(b[i] - b[n]));
if (min(a[i], b[i]) <= b[n] && b[n] <= max(a[i], b[i]))
ext = 0;
}
cout << sum + ext + 1 << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
for _ in range(int(input())):
n, m = map(int, input().split())
bounds = [n, m]
a = []
a.append(list(map(int, input().split())))
a.append(list(map(int, input().split())))
bad = -1
badType = -1
cur = [0, 0]
ans = 0
types = [0 for i in range(n + m + 1)]
for i in range(n + m):
curType = 0
if a[0][i] < a[1][i]:
curType = 1
if cur[curType] == bounds[curType]:
curType = 1 - curType
if bad == -1:
bad = i
badType = 1 - curType
types[i] = curType
ans += a[types[i]][i]
cur[types[i]] += 1
res = []
for i in range(n + m):
val = ans - a[types[i]][i]
if bad != -1 and i < bad and types[i] == badType:
val = val + a[badType][bad] - a[1 - badType][bad] + a[1 - badType][n + m]
else:
val = val + a[types[i]][n + m]
res.append(val)
res.append(ans)
print(*res)
1976D - Invertible Bracket Sequences
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
map<int, int> cnt;
int b = 0;
++cnt[b];
long long ans = 0;
for (auto& c : s) {
b += (c == '(' ? +1 : -1);
ans += cnt[b];
++cnt[b];
while (cnt.begin()->first * 2 < b)
cnt.erase(cnt.begin());
}
cout << ans << '\n';
}
}
1976E - Splittable Permutations
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 300043;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int nxt[N], prv[N];
bool exists[N];
int main()
{
int n, q;
scanf("%d %d", &n, &q);
for(int i = 1; i <= n; i++) nxt[i] = prv[i] = -1;
exists[n] = true;
vector<int> l(q), r(q);
for(int i = 0; i < q; i++) scanf("%d", &l[i]);
for(int i = 0; i < q; i++) scanf("%d", &r[i]);
for(int i = 0; i < q; i++)
{
int L = l[i], R = r[i];
if(exists[L])
{
exists[R] = true;
nxt[R] = nxt[L];
if(nxt[R] != -1) prv[nxt[R]] = R;
prv[R] = L;
nxt[L] = R;
}
else
{
exists[L] = true;
prv[L] = prv[R];
if(prv[L] != -1) nxt[prv[L]] = L;
nxt[L] = R;
prv[R] = L;
}
}
vector<int> seq;
int start = -1;
for(int i = 1; i <= n; i++)
if(prv[i] == -1 && exists[i])
start = i;
seq.push_back(start);
while(nxt[start] != -1)
{
start = nxt[start];
seq.push_back(start);
}
vector<int> cnt_segments(n + 1);
cnt_segments[seq[0]]++;
cnt_segments[seq[q]]++;
for(int i = 0; i < q; i++)
cnt_segments[max(seq[i], seq[i + 1])]++;
int ans = 1;
int places = 0;
for(int i = n; i >= 1; i--)
{
if(exists[i])
places += cnt_segments[i];
else
{
ans = mul(ans, places);
places++;
}
}
printf("%d\n", ans);
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
vector<int> h;
vector<vector<int>> g;
void dfs(int v, int p = -1){
for (int u : g[v]) if (u != p){
dfs(u, v);
h[v] = max(h[v], h[u] + 1);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--){
int n;
cin >> n;
g.assign(n, {});
forn(i, n - 1){
int v, u;
cin >> v >> u;
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
h.assign(n, 0);
dfs(0);
set<pair<int, int>> cur;
forn(i, n) cur.insert({h[i], i});
vector<int> ans;
int tmp = n;
while (!cur.empty()){
int v = cur.rbegin()->second;
while (v != -1){
--tmp;
cur.erase({h[v], v});
int pv = -1;
for (int u : g[v]) if (h[u] == h[v] - 1){
pv = u;
break;
}
v = pv;
}
ans.push_back(tmp);
}
for (int i = 0; i < int(ans.size()); i += 2){
cout << ans[i] << ' ';
}
for (int i = (int(ans.size()) + 1) / 2; i < n - 1; ++i){
cout << 0 << ' ';
}
cout << '\n';
}
return 0;
}