Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int n = s.size();
string a, b;
for (int i = 0; i < 2 * n; ++i) {
a += "()"[i & 1];
b += ")("[i < n];
}
if (a.find(s) == string::npos) {
cout << "YES\n" << a << '\n';
} else if (b.find(s) == string::npos) {
cout << "YES\n" << b << '\n';
} else {
cout << "NO\n";
}
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int m, k, a1, ak;
cin >> m >> k >> a1 >> ak;
int taken_k = m / k;
int taken_1 = m % k;
int taken_fancy_1 = max(0, taken_1 - a1);
int left_regular_1 = max(0, a1 - taken_1);
int taken_fancy_k = max(0, taken_k - ak);
int to_replace = min(left_regular_1 / k, taken_fancy_k);
int ans = taken_fancy_1 + taken_fancy_k - to_replace;
cout << ans << endl;
}
}
Solution 2 (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int m, k, a1, ak;
cin >> m >> k >> a1 >> ak;
// function which calculates the number of fancy coins taken
// if we take exactly x coins of value k
auto f = [m, k, a1, ak](int x)
{
int taken_1 = m - k * x;
return max(0, taken_1 - a1) + max(0, x - ak);
};
int lf = 0;
int rg = m / k;
while(rg - lf > 2)
{
int mid = (lf + rg) / 2;
if(f(mid) < f(mid + 1))
rg = mid + 1;
else
lf = mid;
}
int ans = 1e9;
for(int i = lf; i <= rg; i++) ans = min(ans, f(i));
cout << ans << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 0;
int mn = n + 1, mnWin = n + 1;
while (n--) {
int x;
cin >> x;
if (mn < x && x < mnWin) {
ans += 1;
mnWin = x;
}
mn = min(mn, x);
}
cout << ans << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
const int N = 111;
int n;
string s;
int dp[2][N][N * N];
int main() {
cin >> s;
n = s.size();
dp[0][0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i + 1; ++j) {
for (int cnt = 0; cnt <= j * (i + 1 - j); ++cnt) {
dp[1][j][cnt] = n;
}
}
for (int j = 0; j <= i; ++j) {
for (int cnt = 0; cnt <= j * (i - j); ++cnt) {
dp[1][j + 1][cnt] = min(dp[1][j + 1][cnt], dp[0][j][cnt] + (s[i] != '0'));
dp[1][j][cnt + j] = min(dp[1][j][cnt + j], dp[0][j][cnt] + (s[i] != '1'));
}
}
swap(dp[0], dp[1]);
}
int cnt0 = count(s.begin(), s.end(), '0');
cout << dp[0][cnt0][cnt0 * (n - cnt0) / 2] / 2 << '\n';
}
1860E - Fast Travel Text Editor
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;
const int INF = 1e9;
const int AL = 26;
struct query{
int f, t, ans;
};
struct edge{
int u, w;
};
int main() {
cin.tie(0);
iostream::sync_with_stdio(false);
string s;
cin >> s;
int n = s.size();
int m;
cin >> m;
vector<query> a(m);
forn(i, m){
cin >> a[i].f >> a[i].t;
--a[i].f, --a[i].t;
a[i].ans = abs(a[i].f - a[i].t);
}
int k = n - 1 + AL * AL;
vector<vector<edge>> g(k);
forn(i, n - 1){
int j = n - 1 + (s[i] - 'a') * AL + (s[i + 1] - 'a');
g[i].push_back({j, 0});
g[j].push_back({i, 1});
if (i > 0){
g[i].push_back({i - 1, 1});
g[i - 1].push_back({i, 1});
}
}
for (int st = n - 1; st < k; ++st){
vector<int> d(k, INF);
d[st] = 0;
deque<int> q;
q.push_back(st);
while (!q.empty()){
int v = q.front();
q.pop_front();
for (auto it : g[v]){
if (d[it.u] <= d[v] + it.w) continue;
d[it.u] = d[v] + it.w;
if (it.w == 0) q.push_front(it.u);
else q.push_back(it.u);
}
}
forn(i, m){
a[i].ans = min(a[i].ans, d[a[i].f] + d[a[i].t] - 1);
}
}
forn(i, m) cout << a[i].ans << '\n';
return 0;
}
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;
const int INF = 1e9;
struct bracket{
int a, b, c;
};
struct point{
int x, y;
};
long long cross(const point &a, const point &b){
return a.x * 1ll * b.y - a.y * 1ll * b.x;
}
long long dot(const point &a, const bracket &b){
return a.x * 1ll * b.a + a.y * 1ll * b.b;
}
bool operator <(const point &a, const point &b){
return cross(a, b) > 0;
}
int main() {
int t;
cin >> t;
while (t--){
int n;
cin >> n;
vector<bracket> val;
forn(i, 2 * n){
int a, b;
string c;
cin >> a >> b >> c;
val.push_back({a, b, c[0] == '(' ? 1 : -1});
}
map<point, vector<int>> opts;
forn(i, 2 * n) forn(j, 2 * n){
int dx = val[i].b - val[j].b;
int dy = val[j].a - val[i].a;
if (dx <= 0 || dy <= 0) continue;
opts[{dx, dy}].push_back(i);
opts[{dx, dy}].push_back(j);
}
opts[{1, INF}];
vector<int> ord(2 * n), rord(2 * n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j){
long long di = dot({INF, 1}, val[i]);
long long dj = dot({INF, 1}, val[j]);
if (di != dj) return di < dj;
return val[i].c > val[j].c;
});
forn(i, 2 * n) rord[ord[i]] = i;
int neg = 0, cur = 0;
vector<int> bal(1, 0);
for (int i : ord){
cur += val[i].c;
bal.push_back(cur);
neg += cur < 0;
}
bool ans = neg == 0;
vector<int> prv;
for (auto it : opts){
vector<int> tot = prv;
for (int x : it.second) tot.push_back(x);
sort(tot.begin(), tot.end(), [&](int i, int j){
return rord[i] < rord[j];
});
tot.resize(unique(tot.begin(), tot.end()) - tot.begin());
for (int x : tot) neg -= bal[rord[x] + 1] < 0;
vector<int> tmp = tot;
sort(tot.begin(), tot.end(), [&](int i, int j){
long long di = dot(it.first, val[i]);
long long dj = dot(it.first, val[j]);
if (di != dj) return di < dj;
return val[i].c > val[j].c;
});
vector<int> nrord(tot.size());
forn(i, tot.size()) nrord[i] = rord[tmp[i]];
forn(i, tot.size()) rord[tot[i]] = nrord[i];
for (int x : tot){
bal[rord[x] + 1] = bal[rord[x]] + val[x].c;
neg += bal[rord[x] + 1] < 0;
}
if (neg == 0){
ans = true;
break;
}
prv = it.second;
}
puts(ans ? "YES" : "NO");
}
return 0;
}