Codeforces Round #982 (Div. 2) Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Thank you so much for participating in our round! We really hope you enjoyed it. For us, it was an amazing and educational experience, and we look forward to the possibility that we could one day help to or hold a round again. Thanks again to abc864197532 and Vladithur for making the process so smooth and enjoyable.

2027A - Расстановка прямоугольников

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int maxw = 0, maxh = 0;
        for (int i=0; i<n; i++) {
            int w, h;
            cin >> w >> h;
            maxw = max(maxw, w);
            maxh = max(maxh, h);
        }
        cout << 2 * (maxw + maxh) << "\n";
    }
    return 0;
}

2027B - Сталинская сортировка

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int i=0; i<n; i++) cin >> A[i];
        int best = 0;
        for (int i=0; i<n; i++) {
            int curr = 0;
            for (int j=i; j<n; j++) {
                if (A[j] <= A[i]) {
                    curr += 1;
                }
            }
            best = max(best, curr);
        }
        cout << n - best << "\n";
    }
  return 0;
}

2027C - Добавьте нули

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
        int n;
        cin >> n;
        vector<ll> A(n);
        for (int i=0; i<n; i++) cin >> A[i];
        map<ll,vector<ll>> adj;
        for (int i=1; i<n; i++) {
            ll u = A[i] + i;
            ll v = u + i;
            adj[u].push_back(v);
        }
        set<ll> vis;
        function<void(ll)> dfs = [&](ll u) -> void {
            if (vis.count(u)) return;
            vis.insert(u);
            for (ll v : adj[u]) dfs(v);
        };
        dfs(n);
        cout << *vis.rbegin() << "\n";
  }
  return 0;
}

2027D1 - Финальный диалог (простая версия)

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 1 << 30;

void chmin(int &a, int b) {
  a = min(a, b);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    vector<int> B(m);
    for (int i=0; i<m; i++) cin >> B[i];
    vector nxt(n, vector<int>(m));
    for (int k=0; k<m; k++) {
      int r = -1, sum = 0;
      for (int i=0; i<n; i++) {
        while (r < n && sum <= B[k]) sum += A[++r];
        nxt[i][k] = r;
        sum -= A[i];
      }
    }
    vector dp(n+1, vector<int>(m, inf));
    dp[0][0] = 0;
    for (int k=0; k<m; k++) {
      for (int i=0; i<n; i++) {
        chmin(dp[nxt[i][k]][k], dp[i][k] + m - k - 1);
        if (k < m-1)
          chmin(dp[i][k+1], dp[i][k]);
      }
    }
    int ans = inf;
    for (int k=0; k<m; k++) {
      chmin(ans, dp[n][k]);
    }
    if (ans == inf) {
      cout << "-1\n";
    } else {
      cout << ans << "\n";
    }
  }
  return 0;
}

2027D2 - Финальный диалог (сложная версия)

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 1 << 30;
const int MOD = 1000000007;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    vector<int> B(m);
    for (int i=0; i<m; i++) cin >> B[i];
    vector nxt(n, vector<int>(m));
    for (int k=0; k<m; k++) {
      int r = -1, sum = 0;
      for (int i=0; i<n; i++) {
        while (r < n && sum <= B[k]) sum += A[++r];
        nxt[i][k] = r;
        sum -= A[i];
      }
    }
    vector dp(n+1, vector<array<int,2>>(m, {inf, 0}));
    vector upd(n+1, vector(m, vector<array<int,3>>()));
    upd[0][0].push_back({0, 0, 1});
    upd[1][0].push_back({1, 0, 1});
    for (int k=0; k<m; k++) {
      map<int,array<int,2>> mp;
      for (int i=0; i<=n; i++) {
        for (auto [t, move, count] : upd[i][k]) {
          if (t == 0) {
            auto &[a, b] = mp[move];
            a += 1;
            (b += count) %= MOD;
          } else {
            auto &[a, b] = mp[move];
            a -= 1;
            (b += MOD - count) %= MOD;
            if (a == 0) mp.erase(move);
          }
        }
        if (mp.empty()) continue;
        auto &[move, info] = *mp.begin();
        dp[i][k] = {move, info[1]};
        if (i == n) continue;
        if (k < m-1) {
          upd[i][k+1].push_back({0, move, info[1]});
          upd[i+1][k+1].push_back({1, move, info[1]});
        }
        if (nxt[i][k] > i) {
          upd[i+1][k].push_back({0, move + (m - k - 1), info[1]});
          if (nxt[i][k] < n) {
            upd[nxt[i][k]+1][k].push_back({1, move + (m - k - 1), info[1]});
          }
        }
      }
    }
    map<int,int> mp;
    for (int k=0; k<m; k++) {
      auto &[move, count] = dp[n][k];
      (mp[move] += count) %= MOD;
    }
    auto &[move, count] = *mp.begin();
    if (move == inf) {
      cout << "-1\n";
    } else {
      cout << move << " " << count << "\n";
    }
  }
  return 0;
}

Code(Segment Tree)

#include <bits/stdc++.h>
using namespace std;

#define int long long
int modN = 1e9 + 7;

int mod(int n) {
    return (n + modN) % modN;
}

struct SegmentTree { 
    struct Node {
        int val = 1e18;
        int cnt = 1;
    }; 
 
    vector<Node> st;
    int n;
    SegmentTree(int n): n(n) {
        st.resize(4 * n + 1, Node());
    }
 
    SegmentTree(vector<int> a): n(a.size()) {
        st.resize(4 * n + 1, Node());
        build(a, 1, 0, n - 1);
    }
 
    void merge(Node& a, Node& b, Node& c) {
        a.val = min(b.val, c.val);
        if (b.val == c.val)
            a.cnt = mod(b.cnt + c.cnt);
        else if (b.val < c.val)
            a.cnt = b.cnt;
        else if (b.val > c.val)
            a.cnt = c.cnt;
    }
 
    void build(vector<int>& a, int id, int l, int r) {
        if (l == r) {
            st[id].val = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(a, id * 2, l, mid);
        build(a, id * 2 + 1, mid + 1, r);
        merge(st[id], st[id * 2], st[id * 2 + 1]);
    }
 
    void update(int id, int l, int r, int u, int val, int cnt) {
        if (l == r) {
            st[id].val = val; // or st[id].sum += val
            st[id].cnt = cnt;
            return;
        }
        int mid = (l + r) / 2;
        if (u <= mid) update(id * 2, l, mid, u, val, cnt);
        else update(id * 2 + 1, mid + 1, r, u, val, cnt); 
        merge(st[id], st[id * 2], st[id * 2 + 1]);
    }
 
    void update(int idx, int val, int cnt) { //wrapper
        update(1, 0, n - 1, idx, val, cnt);
    }
 
    Node query(int id, int l, int r, int u, int v) { //give 0, n - 1 as l and r and 1 as id
        if (v < l || r < u) return Node();
        if (u <= l && r <= v) {
            return st[id];
        }
        int mid = (l + r) / 2;
        auto a = query(id * 2, l, mid, u, v);
        auto b = query(id * 2 + 1, mid + 1, r, u, v);
        Node res;
        merge(res, a, b);
        return res;
    }
 
    Node query(int l, int r) { //wrapper
        return query(1, 0, n - 1, l, r);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int &A : a) cin >> A;
    for (int &B : b) cin >> B;
    if (*max_element(a.begin(), a.end()) > b[0]) {
        cout << -1 << '\n';
        return;
    }
    vector<vector<int>> nxt(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        int curr = 0, r = -1;
        for (int j = 0; j < n; j++) {
            while (r + 1 < n && curr + a[r + 1] <= b[i]) 
                curr += a[r + 1], r += 1;
            nxt[i][j] = r + 1;
            if (j <= r) curr -= a[j];
            r = max(r, j);
        }
    }
    vector<SegmentTree> dp(m, SegmentTree(vector<int>(n + 1, 1e18)));
    for (int i = 0; i < m; i++)
        dp[i].update(n, 0, 1);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            auto q1 = dp[j].query(i + 1, nxt[j][i]);
            int v1 = q1.val + m - (j + 1), ps1 = q1.cnt;
            if (i + 1 <= nxt[j][i]) dp[j].update(i, v1, ps1); 
            if (j != m - 1) {
                auto q2 = dp[j + 1].query(i, i);
                int v2 = q2.val, ps2 = q2.cnt;
                auto q3 = dp[j].query(i, i);
                if (v2 < q3.val)
                    dp[j].update(i, v2, ps2);
                else if (v2 == q3.val)
                    dp[j].update(i, v2, mod(ps2 + q3.cnt));
            }
        }
    }
    cout << dp[0].query(0, 0).val << ' ' << dp[0].query(0, 0).cnt << '\n';
}

signed main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t;  
    cin >> t;
    while (t--) 
       solve();
    return 0;
}

2027E1 - Битовая игра (простая версия)

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;

// calculate nimber in O(log A)
int nimber(int x, int a) {
  // find bad positions
  vector<int> badpos;
  int nbits = 0;
  bool pref = 1;
  for (int i=30; i>=0; i--) {
    int mask = 1 << i;
    if ((x & mask) != 0) nbits += 1;
    if ((x & mask) == 0 && (a & mask) != 0) pref = 0;
    if ((x & mask) != 0 && (a & mask) == 0 && pref) badpos.push_back(nbits); 
  }

  // find a'
  int aprime = (1 << nbits) - 1;
  for (int i : badpos) {
    aprime -= 1 << (nbits - i);
  }

  // g(2^k - 2) = 0, for all k >= 1.
  for (int k=1; k<=30; k++) {
    if (aprime == (1 << k) - 2) {
      return 0;
    }
  }

  // g(2^k - 1) = k, for all k >= 1.
  for (int k=1; k<=30; k++) {
    if (aprime == (1 << k) - 1) {
      return k;
    }
  }

  // g(2^k) = k + (-1)^k, for all k >= 0.
  for (int k=1; k<=30; k++) {
    if (aprime == (1 << k)) {
      if (k % 2) return k - 1;
      else return k + 1;
    }
  }

  // g(2^k+1) = g(2^k+2) = ... = g(2^{k+1} - 3) = k + 1, for all k >= 2.
  for (int k=2; k<=30; k++) {
    if ((1 << k) < aprime && aprime <= (2 << k) - 3) {
      return k + 1;
    }
  }

  // should never get to this point
  assert(false);
  return -1;
}

int main() {
  // works in O(n log A)
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    vector<int> X(n);
    for (int i=0; i<n; i++) cin >> X[i];
    int cur = 0;
    for (int i=0; i<n; i++) {
      cur ^= nimber(X[i], A[i]);
    }
    cout << (cur ? "Alice" : "Bob") << "\n";
  }
  return 0;
}

2027E2 - Битовая игра (сложная версия)

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1'000'000'007;

int dp[32][32][3][2][2][3];

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    vector<int> B(n);
    for (int i=0; i<n; i++) cin >> B[i];
    vector<int> curr(32);
    curr[0] = 1;
    for (int i=0; i<n; i++) {
      memset(dp, 0, sizeof dp);

      // dp[i][m][g][fl][gl][hl][il] : 
      // -> m = number of 1s after first good bit
      // -> g = min(2, number of good bits added)
      // -> fl = 1 iff x prefix == high prefix
      // -> gl = 1 iff no x=0 where a=1
      // -> hl = 0 iff no bad bits after first good bit
      //    hl = 1 iff one bad bit after first good bit
      //    hl = 2 iff any one-bit placed after il=1
      int a = A[i];
      int high = B[i];
      dp[0][0][0][1][1][0] = 1;
      for (int i=0; i<=30; i++) {
        int bit = 30 - i;
        int mask = 1 << bit;
        for (int m=0; m<=i; m++) {
          for (int g=0; g<3; g++) {
            for (int fl=0; fl<2; fl++) {
              for (int gl=0; gl<2; gl++) {
                for (int hl=0; hl<3; hl++) {  
                  if (dp[i][m][g][fl][gl][hl] == 0) continue;
                  for (int val=0; val<2; val++) {
                    int fl2 = fl;
                    if (fl && (high & mask) == 0 && val == 1) continue;
                    if (fl && (high & mask) != 0 && val == 0) fl2 = 0;
                    int gl2 = gl;
                    if ((a & mask) != 0 && val == 0) gl2 = 0;
                    bool good = 1;
                    if (gl && (a & mask) == 0 && val == 1) good = 0;
                    int m2 = m;
                    if (g != 0 && val == 1) m2 += 1;
                    int g2 = g;
                    if (g2 < 2 && val == 1 && good) g2 += 1;
                    int hl2 = hl;
                    if (hl == 0 && g > 0 && !good) hl2 = 1;
                    if (hl == 1 && val == 1) hl2 = 2;
                    (dp[i+1][m2][g2][fl2][gl2][hl2] += dp[i][m][g][fl][gl][hl]) %= MOD;
                  }
                }
              }  
            }
          }
        }
      }

      vector<int> here(32);
      for (int m=0; m<32; m++) {
        for (int g=0; g<3; g++) {
          for (int fl=0; fl<2; fl++) {
            for (int gl=0; gl<2; gl++) {
              for (int hl=0; hl<3; hl++) {
                if (dp[31][m][g][fl][gl][hl] == 0) continue;
                if (g == 0) {
                  (here[0] += dp[31][m][g][fl][gl][hl]) %= MOD;
                } else if (hl == 0) {
                  (here[m+1] += dp[31][m][g][fl][gl][hl]) %= MOD;
                } else if (hl == 1) {
                  (here[0] += dp[31][m][g][fl][gl][hl]) %= MOD;
                } else if (g == 1) {
                  int nim = m;
                  if (m % 2) nim -= 1;
                  else nim += 1;
                  (here[nim] += dp[31][m][g][fl][gl][hl]) %= MOD;
                } else {
                  (here[m+1] += dp[31][m][g][fl][gl][hl]) %= MOD;
                }
              }
            }
          }
        }
      }
      
      // remove x=0
      here[0] -= 1;
      
      // update knapsack
      vector<int> next(32);
      for (int i=0; i<32; i++) {
        for (int j=0; j<32; j++) {
          (next[i^j] += 1LL * curr[i] * here[j] % MOD) %= MOD;
        }
      }
      swap(curr, next);
    }
    cout << curr[0] << "\n";
  } 
  return 0;
}

Rev.	By	When	Δ	Comment
en13	myst-6	2024-10-27 12:41:35	2	Tiny change: 'r<int> A(n);\n fo' -> 'r<int> A(n+1);\n fo'
en12	myst-6	2024-10-27 12:32:22	2	Tiny change: 'r<int> A(n);\n fo' -> 'r<int> A(n+1);\n fo'
en11	yud08	2024-10-26 21:27:44	0	(published)
en10	myst-6	2024-10-26 21:18:43	159	Tiny change: 'g from $i$~--- specifica' -> 'g from $i$ — specifica'
en9	yud08	2024-10-26 21:12:54	34
en8	yud08	2024-10-26 21:11:24	2641
en7	yud08	2024-10-26 21:01:32	3575	Tiny change: 'torial">\nFollowin' -> 'torial">\nThe Endspeaker (Hard Version)\nFollowin'
en6	yud08	2024-10-26 20:53:11	3178	Tiny change: 'nt mod = 1'000'000'007;\n \ni' -> 'nt mod = 1000000007;\n \ni'
en5	yud08	2024-10-26 20:48:48	82	Tiny change: 'oiler>\n\n\n<spoil' -> 'oiler>\n\n<spoil'
en4	yud08	2024-10-26 20:44:13	15564	Tiny change: 'spoiler>\n' -> 'spoiler>\n<spoiler summary="Code">\n[model.cpp:2027A]\n</spoiler>\n'
en3	yud08	2024-10-26 20:23:12	3	Tiny change: ' day help or hold a' -> ' day help to or hold a'
en2	yud08	2024-10-26 20:22:07	1
en1	yud08	2024-10-26 20:19:22	984	Initial revision (saved to drafts)

History