Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
x, y, k = map(int, input().split())
if y < x:
print(x)
else:
print(y + max(0, y - x - k))
1895B - Points and Minimum Distance
Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution (fcspartakm)
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
inline void read() {
cin >> n;
a.clear();
for (int i = 0; i < 2 * n; i++) {
int x;
cin >> x;
a.pb(x);
}
}
inline void solve() {
sort(all(a));
vector<pair<int, int> > pts;
for (int i = 0; i < n; i++) {
pts.pb(mp(a[i], a[i + n]));
}
int ans = 0;
for (int i = 1; i < n; i++) {
ans += abs(pts[i].ft - pts[i - 1].ft) + abs(pts[i].sc - pts[i - 1].sc);
}
cout << ans << endl;
for (int i = 0; i < n; i++) {
cout << pts[i].ft << ' ' << pts[i].sc << endl;
}
}
int main () {
int t;
cin >> t;
while (t--){
read();
solve();
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
n = int(input())
s = input().split()
ans = 0
cnt = [[0 for k in range(46)] for k in range(6)]
for y in s:
cnt[len(y)][sum([int(c) for c in y])] += 1
for L in s:
for lenr in range(len(L) % 2, len(L) + 1, 2):
l = len(L) + lenr
suml = sum([int(c) for c in L[:l // 2]])
sumr = sum([int(c) for c in L[l // 2:]])
if suml - sumr >= 0:
ans += cnt[lenr][suml - sumr]
for R in s:
for lenl in range(len(R) % 2, len(R), 2):
l = len(R) + lenl
suml = sum([int(c) for c in R[-l // 2:]])
sumr = sum([int(c) for c in R[:-l // 2]])
if suml - sumr >= 0:
ans += cnt[lenl][suml - sumr]
print(ans)
Idea: AcidWrongGod
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 1; i < n; ++i) {
cin >> a[i];
a[i] ^= a[i - 1];
}
vector<array<int, 2>> t({{-1, -1}});
auto add = [&](int x) {
int v = 0;
for (int i = LOG - 1; i >= 0; --i) {
int j = (x >> i) & 1;
if (t[v][j] == -1) {
t[v][j] = t.size();
t.push_back({-1, -1});
}
v = t[v][j];
}
};
for (int x : a) add(x);
auto get = [&](int x) {
int v = 0;
for (int i = LOG - 1; i >= 0; --i) {
int j = (x >> i) & 1;
if (t[v][j ^ 1] != -1) j ^= 1;
x ^= j << i;
v = t[v][j];
}
return x;
};
for (int x = 0; x < n; ++x) {
if (get(x) == n - 1) {
for (int i : a) cout << (x ^ i) << ' ';
break;
}
}
}
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 card{
int x, y;
card() {}
card(int x, int y) : x(x), y(y) {}
};
void dfs(int v, const vector<int> &g, vector<int> &res, vector<char> &used){
if (used[v]) return;
used[v] = true;
dfs(g[v], g, res, used);
res[v] = -res[g[v]];
}
void solve(){
vector<vector<card>> a(2);
vector<vector<int>> prpos(2);
forn(z, 2){
int n;
scanf("%d", &n);
a[z].resize(n);
forn(i, n) scanf("%d", &a[z][i].x);
forn(i, n) scanf("%d", &a[z][i].y);
sort(a[z].begin(), a[z].end(), [](const card &a, const card &b){
return a.x > b.x;
});
prpos[z].resize(n + 1, -1);
forn(i, n){
if (prpos[z][i] == -1 || a[z][i].y > a[z][prpos[z][i]].y)
prpos[z][i + 1] = i;
else
prpos[z][i + 1] = prpos[z][i];
}
}
int n = a[0].size();
vector<int> g(n + a[1].size());
forn(z, 2) forn(i, a[z].size()){
int cnt = lower_bound(a[z ^ 1].begin(), a[z ^ 1].end(), card(a[z][i].y, -1), [](const card &a, const card &b){
return a.x > b.x;
}) - a[z ^ 1].begin();
g[i + z * n] = prpos[z ^ 1][cnt] == -1 ? -1 : prpos[z ^ 1][cnt] + (z ^ 1) * n;
}
vector<int> res(g.size());
vector<char> used(g.size());
forn(i, g.size()) if (g[i] == -1) res[i] = 1, used[i] = true;
int w = 0, l = 0;
forn(i, n){
if (!used[i]) dfs(i, g, res, used);
w += res[i] == 1;
l += res[i] == -1;
}
printf("%d %d %d\n", w, n - l - w, l);
}
int main(){
int t;
scanf("%d", &t);
while (t--) solve();
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int MOD = 1e9 + 7;
const int N = 40;
using mat = array<array<int, N>, N>;
int add(int x, int y) {
x += y;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
return x;
}
int mul(int x, int y) {
return x * 1LL * y % MOD;
}
mat mul(mat x, mat y) {
mat res;
forn(i, N) forn(j, N) res[i][j] = 0;
forn(i, N) forn(j, N) forn(k, N)
res[i][j] = add(res[i][j], mul(x[i][k], y[k][j]));
return res;
}
template<class T>
T binpow(T x, int y, T e) {
T res = e;
while (y) {
if (y & 1) res = mul(res, x);
x = mul(x, x);
y >>= 1;
}
return res;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, x, k;
cin >> n >> x >> k;
mat a, e;
forn(i, N) forn(j, N) a[i][j] = (i < x && abs(i - j) <= k);
forn(i, N) forn(j, N) e[i][j] = (i == j);
mat b = binpow(a, n - 1, e);
int ans = mul(x + k, binpow(2 * k + 1, n - 1, 1));
forn(i, x) forn(j, x) ans = add(ans, -b[i][j]);
cout << ans << '\n';
}
}
1895G - Two Characters, Two Colors
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(42);
struct node
{
long long x;
int y;
int cnt;
int sum;
int push;
node* l;
node* r;
node() {};
node(long long x, int y, int cnt, int sum, int push, node* l, node* r) : x(x), y(y), cnt(cnt), sum(sum), push(push), l(l), r(r) {};
};
typedef node* treap;
typedef pair<treap, treap> ptt;
int getSum(treap t)
{
return (t ? t->sum : 0);
}
int getCnt(treap t)
{
return (t ? t->cnt : 0);
}
treap fix(treap t)
{
if(!t) return t;
int p = t->push;
if(p != 0)
{
if(t->l) t->l->push += p;
if(t->r) t->r->push += p;
t->x += p;
t->push = 0;
}
t->sum = getSum(t->l) + t->cnt + getSum(t->r);
return t;
}
treap merge(treap a, treap b)
{
a = fix(a);
b = fix(b);
if(!a) return b;
if(!b) return a;
if(a->y > b->y)
{
a->r = merge(a->r, b);
return fix(a);
}
else
{
b->l = merge(a, b->l);
return fix(b);
}
}
bool hasKey(treap t, long long x)
{
t = fix(t);
if(!t) return false;
if(t->x == x) return true;
if(t->x < x) return hasKey(t->r, x);
return hasKey(t->l, x);
}
ptt splitKey(treap t, long long x)
{
t = fix(t);
if(!t) return make_pair(t, t);
if(t->x < x)
{
ptt p = splitKey(t->r, x);
t->r = p.first;
return make_pair(fix(t), p.second);
}
else
{
ptt p = splitKey(t->l, x);
t->l = p.second;
return make_pair(p.first, fix(t));
}
}
long long kthMax(treap t, int k)
{
t = fix(t);
if(!t) return -1;
int sumR = getSum(t->r);
if(sumR >= k) return kthMax(t->r, k);
if(sumR + t->cnt >= k) return t->x;
return kthMax(t->l, k - sumR - t->cnt);
}
int getCntByKey(treap t, long long x)
{
t = fix(t);
if(!t) return 0;
if(t->x == x) return t->cnt;
if(t->x > x) return getCntByKey(t->l, x);
return getCntByKey(t->r, x);
}
treap increaseKey(treap t, long long x, int cnt)
{
t = fix(t);
if(!t) return t;
if(t->x == x)
{
t->cnt += cnt;
}
else if(t->x > x)
{
t->l = increaseKey(t->l, x, cnt);
}
else
{
t->r = increaseKey(t->r, x, cnt);
}
return fix(t);
}
treap insert(treap t, long long x, int y, int cnt)
{
t = fix(t);
if(!t || t->y < y)
{
ptt p = splitKey(t, x);
treap res = new node(x, y, cnt, cnt, 0, p.first, p.second);
return fix(res);
}
if(t->x > x)
t->l = insert(t->l, x, y, cnt);
else
t->r = insert(t->r, x, y, cnt);
return fix(t);
}
treap insertMain(treap t, long long x, int cnt)
{
if(hasKey(t, x))
return increaseKey(t, x, cnt);
else
return insert(t, x, rnd(), cnt);
}
treap eraseKey(treap t, long long x)
{
t = fix(t);
if(!t) return NULL;
if(t->x > x)
{
t->l = eraseKey(t->l, x);
return fix(t);
}
if(t->x < x)
{
t->r = eraseKey(t->r, x);
return fix(t);
}
treap tnew = merge(t->l, t->r);
delete t;
return tnew;
}
ptt splitSum(treap t, int k)
{
t = fix(t);
if(!t) return make_pair(t, t);
if(k == 0) return make_pair(t, treap(NULL));
long long x = kthMax(t, k);
int cnt = getCntByKey(t, x);
t = eraseKey(t, x);
ptt p = splitKey(t, x);
k -= getSum(p.second);
if(k > 0) p.second = merge(new node(x, rnd(), k, k, 0, NULL, NULL), p.second);
if(k < cnt) p.first = merge(p.first, new node(x, rnd(), cnt - k, cnt - k, 0, NULL, NULL));
return p;
}
long long minKey(treap t)
{
t = fix(t);
if(!t) return 1e18;
if(t->l) return minKey(t->l);
return t->x;
}
treap decreaseUpToKLargest(treap t, int k, int& res)
{
if(!k) return t;
t = fix(t);
k = min(k, getSum(t));
res = k;
ptt p = splitSum(t, k);
if(p.second)
{
p.second->push--;
for(int i = 0; i < 2; i++)
{
long long x = minKey(p.second);
int cntMin = getCntByKey(p.second, x);
p.second = eraseKey(p.second, x);
if(x != 0 && cntMin != 0)
p.first = insertMain(p.first, x, cntMin);
}
}
return merge(p.first, p.second);
}
void destroy(treap t)
{
if(!t) return;
if(t->l) destroy(t->l);
if(t->r) destroy(t->r);
delete t;
}
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
vector<long long> r(n), b(n);
for(int i = 0; i < n; i++) cin >> r[i];
for(int i = 0; i < n; i++) cin >> b[i];
long long sum = 0;
for(int i = 0; i < n; i++) sum += r[i] + b[i];
long long flow = 0;
treap t = NULL;
for(int i = 0; i < n; i++)
{
long long d = min(r[i], b[i]);
flow += d;
r[i] -= d;
b[i] -= d;
if(s[i] == '0')
{
int add = 0;
if(r[i] > 1e9) r[i] = 1e9;
t = decreaseUpToKLargest(t, r[i], add);
flow += add;
}
else
{
if(r[i] != 0) t = insertMain(t, r[i], 1);
}
}
cout << sum - flow << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++) solve();
}