Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
print(2 ** n - 1)
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
if 3**(n-1) > 10**9:
print("NO")
else:
print("YES")
print(*[3**x for x in range(n)])
1651C - Fault-tolerant Network
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
typedef long long li;
const int INF = int(1e9);
int n;
vector<int> a, b;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
b.resize(n);
fore (i, 0, n)
cin >> b[i];
return true;
}
int bestCandidate(const vector<int> &vals, int cur) {
int bst = INF + 10, pos = -1;
fore (i, 0, n) {
if (bst > abs(cur - vals[i])) {
bst = abs(cur - vals[i]);
pos = i;
}
}
return pos;
}
inline void solve() {
li bst = 10ll * INF;
vector<int> cds1 = {0, bestCandidate(b, a[0]), n - 1};
vector<int> cds2 = {0, bestCandidate(b, a[n - 1]), n - 1};
for (int var1 : cds1) {
for (int var2 : cds2) {
li ans = (li)abs(a[0] - b[var1]) + abs(a[n - 1] - b[var2]);
if (var1 > 0 && var2 > 0)
ans += abs(b[0] - a[bestCandidate(a, b[0])]);
if (var1 < n - 1 && var2 < n - 1)
ans += abs(b[n - 1] - a[bestCandidate(a, b[n - 1])]);
bst = min(bst, ans);
}
}
cout << bst << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) {
read();
solve();
}
return 0;
}
1651D - Nearest Excluded Points
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (vovuh)
#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
scanf("%d", &n);
vector<pair<int, int>> a(n);
for (auto &[x, y] : a) scanf("%d %d", &x, &y);
set<pair<int, int>> st(a.begin(), a.end());
map<pair<int, int>, pair<int, int>> ans;
queue<pair<int, int>> q;
for (auto [x, y] : a) {
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (st.count({nx, ny})) {
continue;
}
ans[{x, y}] = {nx, ny};
q.push({x, y});
break;
}
}
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (!st.count({nx, ny}) || ans.count({nx, ny})) {
continue;
}
ans[{nx, ny}] = ans[{x, y}];
q.push({nx, ny});
}
}
for (auto [x, y] : a) {
auto it = ans[{x, y}];
printf("%d %d\n", it.first, it.second);
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 3043;
vector<int> g[2 * N];
int n;
int used[2 * N];
int choose2(int n)
{
return n * (n + 1) / 2;
}
int count_ways(int L, int R, const vector<int>& forbidden)
{
if(L > R)
{
int ml = *min_element(forbidden.begin(), forbidden.end());
int mr = *max_element(forbidden.begin(), forbidden.end());
return choose2(ml) + choose2(mr - ml - 1) + choose2(n - 1 - mr);
}
int minl = 0;
int maxl = L;
int minr = R;
int maxr = n - 1;
for(auto x : forbidden)
{
if(L <= x && x <= R)
return 0;
else if(x < L) minl = max(minl, x + 1);
else maxr = min(maxr, x - 1);
}
return (maxl - minl + 1) * (maxr - minr + 1);
}
vector<int> cur;
void dfs(int x)
{
if(used[x] == 1) return;
used[x] = 1;
cur.push_back(x);
for(auto y : g[x]) dfs(y);
}
long long calc(const vector<int>& cycle)
{
int m = cycle.size();
int k = m / 2;
long long ans = 0;
for(int i = 0; i < m; i++)
{
int z = cycle[i];
if(z >= n) z -= n;
ans += choose2(n) * 1ll * (choose2(z) + 0ll + choose2(n - z - 1));
int l = n - 1, r = 0, L = n - 1, R = 0;
int pl = i, pr = i;
for(int j = 0; j < k; j++)
{
for(auto x : vector<int>({cycle[pl], cycle[pr]}))
{
if(x < n)
{
l = min(l, x);
r = max(r, x);
}
else
{
L = min(L, x - n);
R = max(R, x - n);
}
}
vector<int> f, F;
pl--;
if(pl < 0) pl += m;
pr++;
if(pr >= m) pr -= m;
for(auto x : vector<int>({cycle[pl], cycle[pr]}))
{
if(x < n) f.push_back(x);
else F.push_back(x - n);
}
long long add = count_ways(l, r, f) * 1ll * count_ways(L, R, F);
ans += add;
}
}
return ans;
}
int main()
{
cin >> n;
for(int i = 0; i < 2 * n; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
long long ans = n * 1ll * choose2(n) * 1ll * choose2(n) * 2ll;
for(int i = 0; i < n; i++)
{
if(used[i]) continue;
dfs(i);
vector<int> cycle = cur;
ans -= calc(cycle);
cur = vector<int>();
}
cout << ans / 2 << endl;
}
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;
struct node{
node *l, *r;
long long sumc, sumr;
node() : l(NULL), r(NULL), sumc(0), sumr(0) {}
node(node* l, node* r, long long sumc, long long sumr) : l(l), r(r), sumc(sumc), sumr(sumr) {}
};
node* build(int l, int r, vector<int> &c){
if (l == r - 1)
return new node(NULL, NULL, c[l], 0);
int m = (l + r) / 2;
node* nw = new node();
nw->l = build(l, m, c);
nw->r = build(m, r, c);
nw->sumc = nw->l->sumc + nw->r->sumc;
return nw;
}
node* upd(node* v, int l, int r, int pos, int val){
if (l == r - 1)
return new node(NULL, NULL, 0, val);
int m = (l + r) / 2;
node* nw = new node(v->l, v->r, 0, 0);
if (pos < m)
nw->l = upd(v->l, l, m, pos, val);
else
nw->r = upd(v->r, m, r, pos, val);
nw->sumc = nw->l->sumc + nw->r->sumc;
nw->sumr = nw->l->sumr + nw->r->sumr;
return nw;
}
long long getsum(node *v, int mult){
return v->sumc + v->sumr * mult;
}
int trav(node *v, int l, int r, int L, int R, long long &lft, int mult){
if (L >= R){
return 0;
}
if (l == L && r == R && lft - getsum(v, mult) >= 0){
lft -= getsum(v, mult);
return r - l;
}
if (l == r - 1){
return 0;
}
int m = (l + r) / 2;
int cnt = trav(v->l, l, m, L, min(m, R), lft, mult);
if (cnt == max(0, min(m, R) - L))
cnt += trav(v->r, m, r, max(m, L), R, lft, mult);
return cnt;
}
struct seg{
int l, r, lst, cur;
};
int main() {
int n;
scanf("%d", &n);
vector<int> c(n), r(n);
forn(i, n) scanf("%d%d", &c[i], &r[i]);
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y){
return c[x] / r[x] > c[y] / r[y];
});
vector<int> vals;
for (int i : ord) vals.push_back(c[i] / r[i]);
vector<node*> root(1, build(0, n, c));
for (int i : ord)
root.push_back(upd(root.back(), 0, n, i, r[i]));
vector<seg> st;
for (int i = n - 1; i >= 0; --i)
st.push_back({i, i + 1, 0, c[i]});
long long ans = 0;
int q;
scanf("%d", &q);
forn(_, q){
int t;
long long h;
scanf("%d%lld", &t, &h);
while (!st.empty()){
auto it = st.back();
st.pop_back();
if (it.r - it.l == 1){
it.cur = min((long long)c[it.l], it.cur + (t - it.lst) * 1ll * r[it.l]);
if (it.cur <= h){
h -= it.cur;
}
else{
st.push_back({it.l, it.r, t, int(it.cur - h)});
h = 0;
}
}
else{
int mx = vals.rend() - lower_bound(vals.rbegin(), vals.rend(), t - it.lst);
int res = it.l + trav(root[mx], 0, n, it.l, it.r, h, t - it.lst);
assert(res <= it.r);
if (res != it.r){
if (it.r - res > 1)
st.push_back({res + 1, it.r, it.lst, 0});
int nw = min((long long)c[res], r[res] * 1ll * (t - it.lst));
assert(nw - h > 0);
st.push_back({res, res + 1, t, int(nw - h)});
h = 0;
}
}
if (h == 0){
break;
}
}
if (st.empty()){
st.push_back({0, n, t, 0});
}
else if (st.back().l != 0){
st.push_back({0, st.back().l, t, 0});
}
ans += h;
}
printf("%lld\n", ans);
return 0;
}