Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
string s;
cin >> s;
if(s.find("1") < s.find("3"))
cout << 13;
else
cout << 31;
cout << endl;
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int tc = 0; tc < t; ++tc) {
string a, b;
cin >> a >> b;
bool ok = false;
for (int i = 0; i + 1 < a.size(); ++i) {
if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') {
ok = true;
}
}
if (ok)
puts("YES");
else
puts("NO");
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 200000;
int main() {
int t;
cin >> t;
for (int tc = 0; tc < t; ++tc) {
string s;
cin >> s;
int maxSortedPref = 0;
int minNotSortedPref = 0;
int bal = 0;
bool good = true;
for (auto c : s) {
if (c == '+') {
++bal;
} else if (c == '-') {
--bal;
maxSortedPref = min(maxSortedPref, bal);
if (bal < minNotSortedPref)
minNotSortedPref = 0;
} else if (c == '1') {
maxSortedPref = max(maxSortedPref, bal);
} else {
if (bal <= 1) {
good = false;
break;
}
if (minNotSortedPref == 0 || minNotSortedPref > bal)
minNotSortedPref = bal;
}
if(minNotSortedPref <= maxSortedPref && minNotSortedPref != 0) {
good = false;
break;
}
}
if (good)
puts("YES");
else
puts("NO");
}
return 0;
}
Solution 2 (BledDest)
#include<bits/stdc++.h>
using namespace std;
vector<int> has0, has1;
vector<vector<int>> g;
bool ans;
bool dfs(int x, int d)
{
if(has0[x] && (has1[x] || d <= 1))
ans = false;
bool res = false;
for(auto y : g[x])
res |= dfs(y, d + 1);
if(has0[x] && res)
ans = false;
return res || has1[x];
}
void solve()
{
ans = true;
has0.push_back(0);
has1.push_back(0);
g.push_back(vector<int>());
int ts = 1;
string s;
cin >> s;
vector<int> st = {0};
for(auto x : s)
{
int cur = st.back();
if(x == '0')
has0[cur] = 1;
if(x == '1')
has1[cur] = 1;
if(x == '+')
{
g[cur].push_back(ts);
st.push_back(ts);
ts++;
has0.push_back(0);
has1.push_back(0);
g.push_back(vector<int>());
}
if(x == '-')
st.pop_back();
}
dfs(0, 0);
cout << (ans ? "YES\n" : "NO\n");
has0.clear();
has1.clear();
g.clear();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
1861D - Sorting By Multiplication
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 5;
int t;
int n;
int a[N];
int main() {
cin >> t;
for (int tc = 0; tc < t; ++tc){
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
int cnt = 0;
for (int i = 1; i < n; ++i)
cnt += (a[i - 1] >= a[i]);
int res = n, cnt2 = 0;
for (int i = 0; i <= n; ++i) {
bool isMultipliedByNegative = (i > 0);
res = min(res, isMultipliedByNegative + cnt + cnt2);
if (i + 1 < n)
cnt -= (a[i] >= a[i + 1]);
if (i > 0)
cnt2 += (a[i - 1] <= a[i]);
}
cout << res << endl;
}
}
1861E - Non-Intersecting Subpermutations
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
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 sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y & 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int main()
{
int n, k;
cin >> n >> k;
int ans = 0;
vector<vector<int>> dp(n + 1, vector<int>(k, 0));
dp[0][0] = 1;
for(int i = 0; i < n; i++)
{
int cur = 0;
for(int j = k - 1; j >= 1; j--)
{
cur = add(cur, dp[i][j]);
dp[i + 1][j] = cur;
}
for(int j = k - 1; j >= 0; j--)
{
int nxt = (j + 1) % k;
dp[i + 1][nxt] = add(dp[i + 1][nxt], mul(dp[i][j], k - j));
}
ans = add(ans, mul(dp[i + 1][0], binpow(k, n - (i + 1))));
}
cout << ans << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int K = 4;
const int N = 2 * int(1e6) + 43;
pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
return make_pair(a.first + b.first, a.second + b.second);
}
pair<long long, long long> operator-(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
return make_pair(a.first - b.first, a.second - b.second);
}
// prefix sums for an array of pairs
vector<pair<long long, long long>> pref_sums(const vector<pair<long long, long long>>& a)
{
int n = a.size();
vector<pair<long long, long long>> ans(n);
ans[0] = a[0];
for(int i = 1; i < n; i++)
ans[i] = ans[i - 1] + a[i];
return ans;
}
// for an array of pairs denoting linear functions, evaluate
// them in the corresponding points
vector<long long> eval(const vector<pair<long long, long long>>& a)
{
int n = a.size();
vector<long long> ans(n);
for(int i = 0; i < n; i++)
ans[i] = a[i].first * i + a[i].second;
return ans;
}
void solve()
{
int n;
scanf("%d", &n);
vector<vector<int>> a(n, vector<int>(K));
for(int i = 0; i < n; i++)
for(int j = 0; j < K; j++)
scanf("%d", &a[i][j]);
vector<int> b(K);
for(int i = 0; i < K; i++)
scanf("%d", &b[i]);
int deck_size = 0;
for(int i = 0; i < K; i++)
deck_size += b[i];
// calculate the remaining number of cards for each player
long long full = deck_size;
for(int i = 0; i < n; i++)
for(int j = 0; j < K; j++)
full += a[i][j];
vector<int> remain(n, full / n);
for(int i = 0; i < n; i++)
for(int j = 0; j < K; j++)
remain[i] -= a[i][j];
// for every player, calculate the maximum number of cards
// they already have among all suits
// and store it in a multiset
vector<int> min_val(n);
for(int i = 0; i < n; i++)
min_val[i] = *max_element(a[i].begin(), a[i].end());
multiset<int> min_vals;
for(int i = 0; i < n; i++)
min_vals.insert(min_val[i]);
// for every mask of suits and every player, calculate
// the number of cards in those suits they already have
vector<vector<int>> already_has(1 << K, vector<int>(n));
for(int mask = 0; mask < (1 << K); mask++)
for(int i = 0; i < n; i++)
for(int j = 0; j < K; j++)
if(mask & (1 << j))
already_has[mask][i] += a[i][j];
// for every mask of suits and every player, calculate the
// maximum value of x such that if that player can receive
// no more than x cards in each suit, the vertex of that
// player should belong to T in the cut
vector<vector<int>> max_x(1 << K, vector<int>(n));
for(int mask = 0; mask < (1 << K); mask++)
for(int i = 0; i < n; i++)
{
int suits = __builtin_popcount(mask);
if (suits == 0) max_x[mask][i] = N - 2;
else
{
// incoming edges have capacity of
// x - a[i][j]
int incoming = -already_has[mask][i];
// outgoing edge has capacity of remain[i]
// find the maximum x such that
// suits * x + incoming < remains[i]
int x = (remain[i] - incoming) / suits;
x = min(x, N - 2);
max_x[mask][i] = x;
}
}
// for every mask and for all players, calculate the sum of
// values they add to the cut if they can have no more than
// x cards of each suit in the mask
vector<vector<long long>> add_to_cut(1 << K, vector<long long>(N));
for(int mask = 0; mask < (1 << K); mask++)
{
int suits = __builtin_popcount(mask);
vector<pair<long long, long long>> aux(N);
for(int i = 0; i < n; i++)
{
// for the i-th player, they add remains[i] to
// the minimum cut if x > max_x[mask][i]
// otherwise, they add
// suits * x - already_has[mask][i]
int incoming = -already_has[mask][i];
// add [suits * x - incoming] on segment [0, max_x]
int x = max_x[mask][i];
pair<long long, long long> f1 = {suits, incoming};
aux[0] = aux[0] + f1;
aux[x + 1] = aux[x + 1] - f1;
// add remain[i] on [max_x + 1, N)
pair<long long, long long> f2 = {0, remain[i]};
aux[x + 1] = aux[x + 1] + f2;
aux[N - 1] = aux[N - 1] - f2;
}
// sum up those functions and evaluate them
add_to_cut[mask] = eval(pref_sums(aux));
}
// now we're ready to solve the problem!
vector<int> ans(n);
// iterate on the player we want to maximize
for(int i = 0; i < n; i++)
{
// iterate on the suits they will maximize
for(int j = 0; j < K; j++)
{
int d = min(remain[i], b[j]);
int max_cards = a[i][j] + d;
b[j] -= d;
// find the maximum current score over all others
min_vals.erase(min_vals.find(min_val[i]));
int max_rival = *min_vals.rbegin();
min_vals.insert(min_val[i]);
if(max_rival >= max_cards)
ans[i] = max(ans[i], 0);
else
{
// binary search on the maximum cards over all
// opponents
int L = max_rival - 1;
int R = max_cards;
while(R - L > 1)
{
int mid = (L + R) / 2;
long long min_cut = 1e18;
long long req_flow = deck_size - remain[i];
// iterate on the mask of suit vertices
// which belong to S
for(int mask = 0; mask < (1 << K); mask++)
{
int suits = __builtin_popcount(mask);
long long cur_cut = 0;
for(int z = 0; z < K; z++)
if(!(mask & (1 << z)))
cur_cut += b[z];
cur_cut += add_to_cut[mask][mid];
// don't forget to discard our player
// from the flow network!
if(mid > max_x[mask][i])
cur_cut -= remain[i];
else
{
long long add = mid * suits - already_has[mask][i];
cur_cut -= add;
}
min_cut = min(min_cut, cur_cut);
}
if(min_cut < req_flow)
L = mid;
else
R = mid;
}
ans[i] = max(ans[i], max_cards - R);
}
b[j] += d;
}
}
for(int i = 0; i < n; i++)
printf("%d ", ans[i]);
puts("");
}
int main()
{
int t = 1;
for(int i = 0; i < t; i++) solve();
}