We hope you liked our problems!
Tutorial
Tutorial is loading...
Code
t = int(input())
for i in range(t):
a, b, c = map(int, input().split())
if c % 2 == 0:
if a > b:
print("First")
else:
print("Second")
else:
if b > a:
print("Second")
else:
print("First")
Tutorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int solve(int d, vector<int> x)
{
int ans = 0;
for (int i = 1; i < x.size(); i++)
{
ans += (x[i] - x[i - 1] - 1) / d;
}
ans += int(x.size()) - 2;
return ans;
}
void solve()
{
#define tests
int n, m, d;
cin >> n >> m >> d;
vector<int> r(m);
for (int i = 0; i < m; i++) cin >> r[i];
r.insert(r.begin(), 1 - d);
r.push_back(n + 1);
int ans = 2e9;
vector<int> res;
for (int i = 1; i <= m; i++)
{
int A = r[i] - r[i - 1] - 1;
int B = r[i + 1] - r[i] - 1;
int C = r[i + 1] - r[i - 1] - 1;
int D = C / d - (A / d + B / d);
if (D < ans)
{
ans = D;
res.clear();
}
if (D == ans)
{
res.push_back(r[i]);
}
}
cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl;
}
int main()
{
int t = 1;
#ifdef tests
cin >> t;
#endif
while (t--)
{
solve();
}
}
1858C - Yet Another Permutation Problem
Tutorial
Tutorial is loading...
Code
#include<iostream>
#include<vector>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
int cur = 0;
for (int i = 1; i <= n; i += 2) {
for (int j = i; j <= n; j *= 2) {
a[cur++] = j;
}
}
for (int i = 0; i<n; ++i) {
cout << a[i] << " ";
}
cout << '\n';
}
return 0;
}
Tutorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
void solve();
template<typename ...Args>
void println(Args... args) {
apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));
cout << '\n';
}
int32_t main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int t = 1;
cin >> t;
for (int tc = 0; tc < t; ++tc) {
solve();
}
return 0;
}
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> max0by1(n + 1, -1e9);
vector<vector<int>> max0pref(n + 1, vector<int>(n + 1));
vector<vector<int>> max0suf(n + 1, vector<int>(n + 1));
for (int l = 0; l < n; ++l) {
int cnt1 = 0;
for (int r = l + 1; r <= n; ++r) {
cnt1 += s[r - 1] == '1';
max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l);
max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l);
}
}
for (int r = 0; r <= n; ++r) {
for (int cnt = 0; cnt <= n; ++cnt) {
if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]);
if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]);
}
}
for (int l = n; l >= 0; --l) {
for (int cnt = 0; cnt <= n; ++cnt) {
if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]);
if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]);
}
}
vector<int> ans(n + 1, -1e9);
for (int l = 0; l < n; ++l) {
int cnt0 = 0;
for (int r = l; r <= n; ++r) {
if (r > l) cnt0 += s[r - 1] == '0';
if (cnt0 > k) break;
max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]);
max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]);
}
}
for (int i = 0; i <= n; ++i) {
for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
cout << '\n';
}
1858E2 - Rollbacks (Hard Version)
Tutorial
Tutorial is loading...
Code
#include <iostream>
#include <vector>
#include <numeric>
#include <set>
using namespace std;
const int maxn = 1e6 + 1;
int f[maxn];
int get(int i) {
int ans = 0;
while (i >= 0) {
ans += f[i];
i = (i & (i + 1)) - 1;
}
return ans;
}
void upd(int i, int x) {
while (i < maxn) {
f[i] += x;
i = i | (i + 1);
}
}
int a[maxn];
int rev[maxn];
set<int> ids[maxn];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fill(rev, rev + maxn, -1);
fill(a, a + maxn, -1);
int q;
cin >> q;
int ptr = -1;
vector<pair<pair<int, int>, int>> changes;
while (q--) {
char t;
cin >> t;
if (t == '?') {
cout << get(ptr) << endl;
} else if (t == '+') {
int x;
cin >> x;
int mem = a[ptr + 1];
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
ids[a[ptr + 1]].erase(ptr + 1);
}
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
a[ptr + 1] = x;
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
}
ids[x].insert(ptr + 1);
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
++ptr;
changes.push_back({ { 1, mem }, -1 });
} else if (t == '-') {
int k;
cin >> k;
ptr -= k;
changes.push_back({ { -1, k }, -1 });
} else {
if (changes.back().first.first == 1) {
if (a[ptr] != -1) {
if (ids[a[ptr]].size()) {
upd(*ids[a[ptr]].begin(), -1);
ids[a[ptr]].erase(ptr);
}
if (ids[a[ptr]].size()) {
upd(*ids[a[ptr]].begin(), 1);
}
}
a[ptr] = changes.back().first.second;
--ptr;
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
}
ids[a[ptr + 1]].insert(ptr + 1);
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
} else {
ptr += changes.back().first.second;
}
changes.pop_back();
}
}
}
Note: At about 20 minutes into the round one of our testers (SomethingNew) came up with a linear solution for problem E2, and jiangly implemented the same solution shortly after the contest! For further details, see 219001999. The main idea (as jiangly pointed out in the comments) is that we can use prefix sums instead of the Fenwick tree.