Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n, k = map(int, input().split())
for x in range(2):
if n - x * k >= 0 and (n - x * k) % 2 == 0:
print("YES")
break
else:
print("NO")
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
a, b = map(int, input().split())
ans = a + b
for m in range(1, 100000):
ans = min(ans, (a + m - 1) // m + (b + m - 1) // m + (m - 1))
print(ans)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
{
int n;
scanf("%d", &n);
vector<int> s(2);
for(int j = 0; j < 2; j++)
scanf("%d", &s[j]);
vector<pair<int, int>> a(n);
for(int j = 0; j < n; j++)
{
scanf("%d", &a[j].first);
a[j].second = j + 1;
}
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
vector<vector<int>> lists(2);
for(int j = 0; j < n; j++)
{
int cost1 = s[0] * (lists[0].size() + 1);
int cost2 = s[1] * (lists[1].size() + 1);
if(cost1 < cost2)
lists[0].push_back(a[j].second);
else
lists[1].push_back(a[j].second);
}
for(int j = 0; j < 2; j++)
{
cout << lists[j].size();
for(auto x : lists[j]) cout << " " << x;
cout << endl;
}
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readln().toInt()) {
val (n, k) = readln().split(' ').map { it.toInt() }
val f = readln().split(' ').map { it.toLong() }
val d = readln().split(' ').map { it.toLong() }
fun checkAround(pos : Long) : Int {
val qs = Array(2 * k + 1) { MutableList(0) { 0 } }
fun inside(x : Long, pos: Long) = (pos - k <= x) && (x <= pos + k)
for (i in f.indices) {
var newD = maxOf(1L, pos / f[i])
if (newD != d[i] && newD + 1 != d[i] && inside(d[i] * f[i], pos)) {
val id = (i + 1)
qs[(d[i] * f[i] - pos + k).toInt()].add(id)
}
repeat(2) {
if (inside(newD * f[i], pos)) {
val id = if (newD == d[i]) (i + 1) else -(i + 1)
qs[(newD * f[i] - pos + k).toInt()].add(id)
}
newD++
}
}
val cntPerId = IntArray(n) { 0 }
var cntDistinct = 0
var cntGood = 0
fun addToSeg(cid : Int) {
val id = -1 + if (cid > 0) cid else -cid
val c = if (cid > 0) 1 else 0
if (cntPerId[id] == 0)
cntDistinct++
cntPerId[id]++
cntGood += c
}
fun eraseFromSeg(cid : Int) {
val id = -1 + if (cid > 0) cid else -cid
val c = if (cid > 0) 1 else 0
cntPerId[id]--
if (cntPerId[id] == 0)
cntDistinct--
cntGood -= c
}
var ans = 0
for (p in 0 until k)
qs[p].forEach { addToSeg(it) }
for (p in 0..k) {
qs[p + k].forEach { addToSeg(it) }
if (cntDistinct == n)
ans = maxOf(ans, cntGood)
qs[p].forEach { eraseFromSeg(it) }
}
return n - ans
}
var ans = n
for (i in f.indices) {
ans = minOf(ans, checkAround(d[i] * f[i]))
}
println(ans)
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
const li INF = (li)(1e18);
const int N = 200043;
struct data
{
array<array<long long, 2>, 2> d;
data() {
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
d[i][j] = INF;
};
data(li x)
{
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
d[i][j] = INF;
d[0][0] = 0;
d[1][1] = x;
};
data(data l, data r)
{
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
d[i][j] = INF;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
for(int x = 0; x < 2; x++)
{
if(j == 0 && k == 0) continue;
d[i][x] = min(d[i][x], l.d[i][j] + r.d[k][x]);
}
};
};
data T[4 * N];
li a[N];
void recalc(int v)
{
T[v] = data(T[v * 2 + 1], T[v * 2 + 2]);
}
void build(int v, int l, int r)
{
if(l == r - 1) T[v] = data(a[l]);
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
recalc(v);
}
}
void upd(int v, int l, int r, int pos, li val)
{
if(l == r - 1)
{
a[l] = val;
T[v] = data(a[l]);
}
else
{
int m = (l + r) / 2;
if(pos < m)
upd(v * 2 + 1, l, m, pos, val);
else
upd(v * 2 + 2, m, r, pos, val);
recalc(v);
}
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n - 1; i++)
{
scanf("%lld", &a[i]);
}
build(0, 0, n - 1);
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
int x;
li k;
scanf("%d %lld", &x, &k);
upd(0, 0, n - 1, x - 1, k);
printf("%lld\n", T[0].d[1][1] * 2);
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
const int N = 200002;
const int V = 50 * N;
using pt = pair<int, int>;
int n, m;
pt a[N];
vector<pt> t[4 * N];
int p[N], rk[N], vs[N];
int cntV;
pt g[V];
bool ans[V];
void upd(int v, int l, int r, int L, int R, pt e) {
if (L >= R) return;
if (l == L && r == R) {
t[v].push_back(e);
return;
}
int m = (l + r) / 2;
upd(v * 2 + 1, l, m, L, min(m, R), e);
upd(v * 2 + 2, m, r, max(m, L), R, e);
}
int k;
int* ptr[V];
int val[V];
void upd(int &a, int b) {
ptr[k] = &a;
val[k] = a;
k += 1;
a = b;
}
int getp(int v) {
return p[v] == v ? v : getp(p[v]);
}
void unite(int v, int u) {
v = getp(v), u = getp(u);
if (v == u) return;
if (rk[v] > rk[u]) swap(v, u);
upd(p[v], u);
g[cntV] = {vs[v], vs[u]};
upd(vs[u], cntV++);
if (rk[v] == rk[u])
upd(rk[u], rk[u] + 1);
}
void solve(int v, int l, int r) {
int cur = k;
for (auto& [v, u] : t[v])
unite(v, u);
if (l + 1 == r) {
ans[vs[getp(0)]] = 1;
} else {
int m = (l + r) / 2;
solve(v * 2 + 1, l, m);
solve(v * 2 + 2, m, r);
}
while (k > cur) {
k -= 1;
(*ptr[k]) = val[k];
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> a[i].first >> a[i].second;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x; --y;
int L = max(a[x].first, a[y].first);
int R = min(a[x].second, a[y].second);
upd(0, 0, N, L, R + 1, {x, y});
}
for (int i = 0; i < n; ++i) {
p[i] = i;
rk[i] = 1;
vs[i] = i;
g[i] = {-1, -1};
}
cntV = n;
solve(0, 0, N);
queue<int> q;
for (int i = 0; i < cntV; ++i) if (ans[i])
q.push(i);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : {g[v].first, g[v].second}) {
if (u != -1 && !ans[u]) {
ans[u] = true;
q.push(u);
}
}
}
for (int i = 0; i < n; ++i) if (ans[i])
cout << i + 1 << ' ';
}