Codeforces Global Round 5 Editorial

Revision en1, by tourist, 2019-10-16 21:41:29

Enjoy!

A. Balanced Rating Changes
Tutorial is loading...
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
Tutorial is loading...
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)
Tutorial is loading...
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)
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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;
vector<pair<int, vector<ll>>> answer;

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];
    answer.pb({start, exchange});
    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);
    
    assert((int)answer.size() == ans.fi);
    printf("%d\n", (int)answer.size());
    for (auto &t : answer)
    {
        printf("%d", (t.fi + ans.se) % n);
        for (auto tt : t.se) printf(" %lld", tt);
        printf("\n");
    }
    return 0;
}
H. Balanced Reversals
Tutorial is loading...
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;
vector<int> answer;
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;
}

inline void addanswer(int x)
{
    if (x <= 0) return;
    answer.pb(x);
}

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);
        
        answer.clear();
        addanswer(before);
        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;
            addanswer(2 * wh);
            doreverse(ss, wh);
            addanswer(2 * wh + 2);
            doreverse(ss, wh + 1);
        }
        addanswer(after);
        
        for (auto t : answer) reverse(s, s + t);
        assert(strcmp(s, t) == 0);
        
        printf("%d ", (int)answer.size());
        for (auto t : answer) printf("%d ", t);
        printf("\n");
    }
    return 0;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English tourist 2019-10-16 21:41:29 14722 Initial revision (published)