Codeforces Global Round 5 Editorial

Правка en1, от tourist, 2019-10-16 21:41:29

Enjoy!

A. Balanced Rating Changes
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int flag = 1;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 0) {
cout << x / 2 << '\n';
} else {
cout << (x + flag) / 2 << '\n';
flag *= -1;
}
}
return 0;
}

B. Balanced Tunnel
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
--b[i];
}
vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[b[i]] = i;
}
vector<int> c(n);
for (int i = 0; i < n; i++) {
c[i] = pos[a[i]];
}
int mx = -1, ans = 0;
for (int i = 0; i < n; i++) {
if (c[i] > mx) {
mx = c[i];
} else {
++ans;
}
}
cout << ans << '\n';
return 0;
}

C1. Balanced Removals (Easier)
Solution by arsijo
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<pair<int, int>, pair<int, int> > ii;

int main(){
int n;
cin >> n;

vector<ii> v(n);
for (int i = 0; i < n; i++){
cin >> v[i].first.first >> v[i].first.second >> v[i].second.first;
v[i].second.second = i + 1;
}

while(!v.empty()){
sort(v.begin(), v.end());
int x = v.back().first.first;
int y = v.back().first.second;
int z = v.back().second.first;
int pos = v.back().second.second;
v.pop_back();
int ind = 0;
ll d = 1e10;
for (int i = 0; i < (int) v.size(); i++){
ll dist = abs(v[i].first.first - x);
dist += abs(v[i].first.second - y);
dist += abs(v[i].second.first - z);
if (dist < d){
d = dist;
ind = i;
}
}
cout << pos << " " << v[ind].second.second << endl;
v.erase(v.begin() + ind);
}
}

C2. Balanced Removals (Harder)
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

const int D = 3;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<int>> p(n, vector<int>(D));
for (int i = 0; i < n; i++) {
for (int j = 0; j < D; j++) {
cin >> p[i][j];
}
}
auto Solve = [&](auto& Self, vector<int> ids, int k) {
if (k == D) {
return ids[0];
}
map<int, vector<int>> mp;
for (int x : ids) {
mp[p[x][k]].push_back(x);
}
vector<int> a;
for (auto& q : mp) {
int cur = Self(Self, q.second, k + 1);
if (cur != -1) {
a.push_back(cur);
}
}
for (int i = 0; i + 1 < (int) a.size(); i += 2) {
cout << a[i] + 1 << " " << a[i + 1] + 1 << '\n';
}
return (a.size() % 2 == 1 ? a.back() : -1);
};
vector<int> t(n);
iota(t.begin(), t.end(), 0);
Solve(Solve, t, 0);
return 0;
}

D. Balanced Playlist
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(3 * n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i + n] = a[i + 2 * n] = a[i];
}
vector<int> ans(3 * n);
vector<int> st_max;
vector<int> st_min;
for (int i = 3 * n - 1; i >= 0; i--) {
while (!st_max.empty() && a[st_max.back()] < a[i]) {
st_max.pop_back();
}
while (!st_min.empty() && a[st_min.back()] > a[i]) {
st_min.pop_back();
}
int low = 0, high = (int) st_min.size();
while (low < high) {
int mid = (low + high) >> 1;
if (a[st_min[mid]] * 2 < a[i]) {
low = mid + 1;
} else {
high = mid;
}
}
int nxt = 3 * n;
if (low > 0) {
nxt = min(nxt, st_min[low - 1]);
}
if (!st_max.empty()) {
nxt = min(nxt, st_max.back());
}
if (nxt < 3 * n && a[nxt] >= a[i]) {
ans[i] = ans[nxt];
} else {
ans[i] = nxt;
}
st_min.push_back(i);
st_max.push_back(i);
}
for (int i = 0; i < n; i++) {
if (i > 0) {
cout << " ";
}
cout << (ans[i] == 3 * n ? -1 : ans[i] - i);
}
cout << '\n';
return 0;
}

E. Balanced Binary Search Trees
Solution by tourist
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int x = 1;
while (x <= n) {
if (n == x || n == x + 1) {
cout << 1 << '\n';
return 0;
}
if (x % 2 == 0) {
x = x + 1 + x;
} else {
x = (x + 1) + 1 + x;
}
}
cout << 0 << '\n';
return 0;
}

F. Balanced Domino Placements
Solution by arsijo
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 998244353;
const int MAX = 3610;
ll dp1[MAX][MAX], dp2[MAX][MAX];
int has1[MAX], has2[MAX];
ll fac[MAX], c[MAX][MAX];
int n, m, k;

void make(int n){
dp1[0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= m; j++){
dp1[i][j] = dp1[i - 1][j];
if (j && i >= 2 && has1[i] == 0 && has1[i - 1] == 0){
dp1[i][j] += dp1[i - 2][j - 1];
}
dp1[i][j] %= MOD;
}
}
}

int main(){
cin >> n >> m >> k;
int t = max(n, m) + 1;
vector<ll> f(t);
for (int i = 1; i <= k; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
if (has1[a] || has1[c] || has2[b] || has2[d]){
cout << 0 << endl;
return 0;
}
has1[a] = has1[c] = has2[b] = has2[d] = 1;
}
int N = n, M = m;
for (int i = 1; i <= n; i++){
N -= has1[i];
}
for (int i = 1; i <= m; i++){
M -= has2[i];
}
make(n);
swap(dp1, dp2);
swap(has1, has2);
make(m);
swap(dp1, dp2);
swap(has1, has2);
c[0][0] = 1;
f[0] = 1;
for (int i = 1; i < t; i++){
f[i] = (f[i - 1] * i) % MOD;
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++){
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
if (c[i][j] >= MOD){
c[i][j] -= MOD;
}
}
}
ll ans = 0;
for (int i = 0; (i << 1) <= N; i++){
for (int j = 0; (j << 1) <= M; j++){
int have1 = N - 2 * i;
int have2 = M - 2 * j;
ll res = dp1[n][i] * dp2[m][j];
res %= MOD;
res *= c[have1][j];
res %= MOD;
res *= c[have2][i];
res %= MOD;
res *= f[i];
res %= MOD;
res *= f[j];
res %= MOD;
ans += res;
}
}
ans %= MOD;
cout << ans << endl;
}

G. Balanced Distribution
Solution by KAN
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 200005;
const int maxk = 19;
const int inf = 1e9;

ll a[2 * maxn];
ll psum[2 * maxn];
pair2<int> go[maxk][2 * maxn];
map<ll, int> lst[maxn];
int id[2 * maxn];
int n, k;
ll need;

void perform(int l)
{
int fn = min(l + k, n);
assert(psum[fn] >= 0);
ll wassum = psum[fn];
vector<ll> exchange = vector<ll>(k, need);
int start = min(n - k, l);
for (int i = start; i < l; i++) exchange[i - start] = need + a[i];
exchange[l - start] += -psum[l];
exchange.back() += psum[fn];
for (int i = l; i < fn; i++) a[i] = 0;
a[l] += -psum[l];
a[fn - 1] += psum[fn];
for (int i = start; i < start + k; i++) psum[i + 1] = psum[i] + a[i];
assert(wassum == psum[fn]);
}

void restore(int l)
{
if (l >= n) return;
if (a[l] == 0 && psum[l] == 0)
{
restore(l + 1);
return;
}
int fn = min(l + k, n);
if (psum[fn] >= 0)
{
perform(l);
restore(l + k - (psum[fn] > 0));
return;
} else
{
restore(l + k - 1);
assert(psum[fn] == 0);
perform(l);
}
}

int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
need = accumulate(a, a + n, 0LL);
assert(need % n == 0);
need /= n;
for (int i = 0; i < n; i++) a[i] -= need;
for (int i = 0; i < n; i++) a[i + n] = a[i];
partial_sum(a, a + 2 * n, psum + 1);
pair2<int> ans = {inf, -1};
for (int j = 0; j < maxk; j++) go[j][2 * n] = {2 * n, 0};
for (int i = 2 * n - 1; i >= 0; i--)
{
int curid = id[i + 1];
if (lst[curid].count(psum[i]))
{
int to = lst[curid][psum[i]];
go[0][i] = {to, (to - i - 1) / (k - 1)};
} else
{
int to = 2 * n;
go[0][i] = {to, (to - i + k - 2) / (k - 1)};
}
for (int j = 1; j < maxk; j++) go[j][i] = {go[j - 1][go[j - 1][i].fi].fi, go[j - 1][i].se + go[j - 1][go[j - 1][i].fi].se};

if (i < n)
{
int to = n + i;
int cur = i;
int curans = 0;
for (int j = maxk - 1; j >= 0; j--) if (go[j][cur].fi <= to)
{
curans += go[j][cur].se;
cur = go[j][cur].fi;
}
if (cur < to) curans += (to - cur - 1 + k - 2) / (k - 1);
ans = min(ans, {curans, i});
}

id[i] = (2 * n - i) % (k - 1);
lst[id[i]][psum[i]] = i;
}

rotate(a, a + ans.se, a + n);
partial_sum(a, a + n, psum + 1);
restore(0);

{
printf("%d", (t.fi + ans.se) % n);
for (auto tt : t.se) printf(" %lld", tt);
printf("\n");
}
return 0;
}

H. Balanced Reversals
Solution by KAN
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 4005;

vector<int> ss, tt;
char s[maxn], t[maxn];
int n;
int cnt[5];

vector<int> prepare(char *s)
{
vector<int> ans;
for (int i = 0; i < 2 * n; i += 2) ans.pb((s[i] - '0') * 2 + (s[i + 1] - '0'));
return ans;
}

{
if (x <= 0) return;
}

void doreverse(vector<int> &v, int l)
{
reverse(v.begin(), v.begin() + l);
for (int j = 0; j < l; j++) if (v[j] >= 1 && v[j] <= 2)
{
v[j] = 3 - v[j];
}
}

int main()
{
int NT;
scanf("%d", &NT);
for (int T = 0; T < NT; T++)
{
scanf("%s%s", s, t);
n = strlen(s) / 2;
ss = prepare(s);
tt = prepare(t);
for (auto &t : tt) if (t == 1 || t == 2) t = 3 - t;
cnt[0] = cnt[1] = cnt[2] = cnt[3] = 0;
for (auto t : ss) cnt[t]++;
for (auto t : tt) cnt[t]--;
if (cnt[0] != 0 || cnt[3] != 0)
{
printf("-1\n");
continue;
}
bool found = cnt[1] == 0;
int before = -1;
int after = -1;
for (int i = 1; i <= n && !found; i++)
{
cnt[ss[i - 1]]--;
cnt[3 - ss[i - 1]]++;
if (cnt[1] == 0)
{
before = 2 * i;
doreverse(ss, i);
found = true;
}
}
if (!found)
{
for (int i = 1; i <= n; i++)
{
cnt[ss[i - 1]]++;
cnt[3 - ss[i - 1]]--;
}
}
for (int i = 1; i <= n && !found; i++)
{
cnt[tt[i - 1]]++;
cnt[3 - tt[i - 1]]--;
if (cnt[1] == 0)
{
after = 2 * i;
doreverse(tt, i);
found = true;
}
}
assert(found);

for (int i = n - 1; i >= 0; i--)
{
int wh = -1;
for (int j = n - 1 - i; j < n; j++) if (ss[j] == tt[i]) wh = j;
doreverse(ss, wh);
doreverse(ss, wh + 1);
}

for (auto t : answer) reverse(s, s + t);
assert(strcmp(s, t) == 0);

for (auto t : answer) printf("%d ", t);
printf("\n");
}
return 0;
}


#### История

Правки

Rev. Язык Кто Когда Δ Комментарий
en1 tourist 2019-10-16 21:41:29 14722 Initial revision (published)