231849364

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  cout << s.back() << '\n';
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

• Didnt solve
• Good problem
• Average problem
• Bad problem
• tROlll pRoBlEm

231849397

#include <bits/stdc++.h>
 
using namespace std;
const int N = 100;
 
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> b(n, 1);
  vector<vector<int>> inds(N + 1);
  for (int i = 0; i < n; i++) {
    inds[a[i]].push_back(i);
  }
  int k = 2;
  for (int x = 1; x <= N; x++) {
    if ((int) inds[x].size() >= 2) {
      b[inds[x][0]] = k;
      k++;
      if (k > 3) {
        break;
      }
    }
  }
  if (k <= 3) {
    cout << "-1\n";
  } else {
    for (int i = 0; i < n; i++) {
      cout << b[i] << ' ';
    }
    cout << '\n';
  }
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

• Didnt solve
• Good problem
• Average problem
• Bad problem

231849420

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  k = min(k, n);
  int last = n - 1;
  for (int _ = 0; _ < k; _++) {
    if (a[last] > n) {
      cout << "No\n";
      return;
    }
    last += n - a[last];
    if (last >= n) {
      last -= n;
    }
  }
  cout << "Yes\n";
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

• Didnt solve
• Good problem
• Average problem
• Bad problem

231849445

#include <bits/stdc++.h>
 
#define pb push_back
#define all(x) x.begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()
using namespace std;
 
void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(m), c(n + m);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  sort(rall(b));
  merge(all(a), all(b), c.begin(), greater<int>());
  for (int i = 0; i < n + m; i++) {
    cout << c[i] << ' ';
  }
  cout << '\n';
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

• Didnt solve
• Good problem
• Average problem
• Bad problem

231849477

#include <bits/stdc++.h>
 
#define pb push_back
#define int long long
#define all(x) x.begin(), (x).end()
using namespace std;
 
void solve() {
  int m;
  cin >> m;
  vector<int> n(m), l(m), r(m);
  vector<vector<int>> a(m);
  vector<vector<int>> c(m);
  vector<int> sumc(m);
  int suml = 0, sumr = 0, sumn = 0;
  for (int i = 0; i < m; i++) {
    cin >> n[i] >> l[i] >> r[i];
    sumn += n[i];
    suml += l[i];
    sumr += r[i];
    a[i].resize(n[i]);
    for (int j = 0; j < n[i]; j++) {
      cin >> a[i][j];
    }
    c[i].resize(n[i]);
    for (int j = 0; j < n[i]; j++) {
      cin >> c[i][j];
      sumc[i] += c[i][j];
    }
  }
  
  if (sumr - suml > sumn) {
    cout << "0\n";
    return;
  }
 
  map<int, int> sumr_a;
  map<int, vector<pair<int, int>>> indexes;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n[i]; j++) {
      sumr_a[a[i][j]] += r[i];
      indexes[a[i][j]].pb({i, j});
    }
  }
 
  int ans = (int) 2e18;
  for (int len = suml; len <= sumr; len++) {
    int xsize = 0, must_len = 0;
    xsize += sumr - sumr_a[len];
    for (auto &[i, pos] : indexes[len]) {
      int cnt_not_len = sumc[i] - c[i][pos];
      if (cnt_not_len < l[i]) {
        xsize += l[i];
        must_len += l[i] - cnt_not_len;
      } else {
        xsize += min(cnt_not_len, r[i]);
      }
    }
    ans = min(ans, must_len + max(0LL, len - xsize));
  }
  cout << ans << '\n';
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

• Didnt solve
• Good problem
• Average problem
• Bad problem

231849510

#include <bits/stdc++.h>
 
#define pb push_back
#define all(x) x.begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()
using namespace std;
 
void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> s(m), d(m);
  for (int i = 0; i < m; i++) {
    cin >> s[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> d[i];
  }
  vector<int> cnt(n + 1);
  for (int i = 0; i < n; i++) {
    cnt[a[i]]++;
  }
 
  set<pair<int, int>> cubes;
  for (int x = 1; x <= n; x++) {
    if (cnt[x] == 0) continue;
    cubes.insert({cnt[x], x});
  }
 
  vector<vector<int>> ans(m);
 
  for (int i = 0; i < m; i++) {
    ans[i].assign(s[i], 0);
    for (int j = 0; j < s[i]; j++) {
      if (j >= d[i]) {
        if (cnt[ans[i][j - d[i]]] > 0) {
          cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]});
        }
      }
      if (cubes.empty()) {
        cout << "-1\n";
        return;
      }
      ans[i][j] = (*cubes.rbegin()).second;
      cubes.erase(*cubes.rbegin());
      cnt[ans[i][j]]--;
    }
    for (int j = s[i]; j < s[i] + d[i]; j++) {
      if (cnt[ans[i][j - d[i]]] > 0) {
        cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]});
      }
    }
  }
 
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < s[i]; j++) {
      cout << ans[i][j] << ' ';
    }
    cout << '\n';
  }
 
}
 
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

• Didnt solve
• Good problem
• Average problem
• Bad problem

231849553

#include <bits/stdc++.h>
 
typedef long long ll;
#define pb push_back
 
using namespace std;
 
const int M = 998244353;
const int N = 500500;
vector<pair<int, int>> g[N];
set<int> bridgesV[N];
bitset<N> used;
int h[N], d[N];
ll bridges = 0;
ll solo = 0;
 
int binpow(ll a, ll x) {
  ll ans = 1;
  while (x) {
    if (x % 2) {
      ans *= a;
      ans %= M;
    }
    a *= a;
    a %= M;
    x /= 2;
  }
  return (int) ans;
}
 
void dfs(int v, int p = -1) {
  if (p != -1) {
    d[v] = h[p] + 1;
    h[v] = h[p] + 1;
  }
  used[v] = true;
  for (auto &[u, w] : g[v]) {
    if (u == p) continue;
    if (!used[u]) {
      dfs(u, v);
      d[v] = min(d[v], d[u]);
      if (h[v] < d[u]) {
        bridgesV[v].insert(u);
        bridgesV[u].insert(v);
        bridges += w + 1;
        solo += w;
      }
    } else {
      d[v] = min(d[v], h[u]);
    }
  }
}
 
int calc_dp(ll n) {
  n %= (M - 1);
  if (n == 1) return 3;
  if (n == 2) return 0;
  int val = binpow(2, n);
  if (n % 2 == 1) {
    val += M - 2;
  } else {
    val += 2;
  }
  val %= M;
  return val;
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    a--;
    b--;
    g[a].pb({b, w});
    g[b].pb({a, w});
  }
  if (n % 2 != m % 2) {
    cout << "0\n";
    return 0;
  }
  dfs(0);
  used.reset();
 
  ll ans = 1;
  for (int v = 0; v < n; v++) {
    if (!used[v]) {
      ll cs = 0;
      vector<int> q = {v};
      used[v] = true;
      while (!q.empty()) {
        int u = q.back();
        q.pop_back();
        for (auto &[uu, w] : g[u]) {
          if (bridgesV[u].find(uu) != bridgesV[u].end()) continue;
          cs += w + 1;
          if (!used[uu]) {
            used[uu] = true;
            q.pb(uu);
          }
        }
      }
      cs /= 2;
      cs = max(cs, 1LL);
      ans *= calc_dp(cs);
      ans %= M;
    }
  }
  ans *= binpow(3, solo);
  ans %= M;
  int w = (2 * binpow(3, M - 2)) % M;
  ans *= binpow(w, bridges);
  ans %= M;
  int cycles = (m + 1) - n;
  ans *= binpow(2, cycles);
  ans %= M;
  cout << ans << '\n';
}

• Didnt solve
• Good problem
• Average problem
• Bad problem

222362736

222362772

222362796

222362817

222362852

222362879

222437122

• ✅ Read all problems
• ✅ Don't be afraid to skip problems and come back to them later (or not come back at all)
• ✅ Maximize your enjoyment of the contest, not your rating after it

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    for i in range(n):
        if a[i] > b[i]:
            a[i], b[i] = b[i], a[i]
    if a[-1] == max(a) and b[-1] == max(b):
        print("YES")
    else:
        print("NO")

• Didnt solve
• Good problem
• Average problem
• Bad problem

MAX = 50000
last = [0] * (MAX + 777)
for _ in range(int(input())):
    m = int(input())
    a_ = []
    for day in range(m):
        n = int(input())
        a = list(map(int, input().split()))
        for x in a:
            last[x] = day
        a_.append(a)
    ans = [-1] * m
    for day in range(m):
        for x in a_[day]:
            if last[x] == day:
                ans[day] = x
        if ans[day] == -1:
            print(-1)
            break
    else:
        print(*ans)

• Didnt solve
• Good problem
• Average problem
• Bad problem

from math import gcd
 
def lcm(a, b):
  return a * b // gcd(a, b)
 
for _ in range(int(input())):
    n = int(input())
    a = []
    b = []
    for i in range(n):
       ai, bi = map(int, input().split())
       a.append(ai)
       b.append(bi)
    g = 0
    l = 1
    ans = 1
    for i in range(n):
        g = gcd(g, a[i] * b[i])
        l = lcm(l, b[i])
        if g % l:
            ans += 1
            g = a[i] * b[i]
            l = b[i]
    print(ans)

• Didnt solve
• Good problem
• Average problem
• Bad problem

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if max(a) == 0:
        print("No")
    else:
        print("Yes")
        prefix_sum = 0
        pos = []
        neg = []
        for x in a:
            if x >= 0:
                pos.append(x)
            else:
                neg.append(x)
        ans = []
        for _ in range(n):
            if prefix_sum <= 0:
                ans.append(pos[-1])
                pos.pop()
            else:
                ans.append(neg[-1])
                neg.pop()
            prefix_sum += ans[-1]
        print(' '.join(list(map(str, ans))))

• Didnt solve
• Good problem
• Average problem
• Bad problem

N = 300777
a = [0] * N
go = [0] * N
good_chain = [0] * N
chain_depth = [0] * N
suf_max_chain_depth = [0] * N

ans = ""
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    chain_depth[n + 1] = 0
    suf_max_chain_depth[n + 1] = 0
    curr_max_chain_depth = 0
    for i in range(n, 0, -1):
        go[i] = i + a[i] + 1
        if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]):
            good_chain[i] = True
        else:
            good_chain[i] = False
        chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)]
        suf_max_chain_depth[i] = 1 + curr_max_chain_depth
        if go[i] <= n + 1:
            suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]])
        if good_chain[i]:
            curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i])
    for i in range(1, n):
        if good_chain[i + 1] and chain_depth[i + 1] == a[i]:
            ans += "0 "
        elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]:
            ans += "1 "
        else:
            ans += "2 "
    ans += '\n'
print(ans)

• Didnt solve
• Good problem
• Average problem
• Bad problem

#include <bits/stdc++.h>
 
#define pb push_back
// #define int long long
#define all(x) x.begin(), x.end()
#define ld long double
using namespace std;
const int N = 210;
bool dp[N][N][N];
bool take[N][N][N];
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n), s(k);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> s[i];
    }
    vector<pair<int, int>> s2;
    for (int i = 0; i < k; i++) {
        s2.pb({s[i], i});
    }
    sort(all(s2));
    vector<vector<int>> ans(k);
    for (int i = 0; i < k - 1; i++) {
        int class_size = s2[i].first;
        vector<int> boxes;
        for (int _ = 0; _ < 2 * class_size - 1; _++) {
            boxes.pb(a.back());
            a.pop_back();
        }
        for (int sz = 0; sz <= class_size; sz++) {
            for (int r = 0; r < class_size; r++) {
                dp[0][sz][r] = false;
                take[0][sz][r] = false;
            }
        }
        dp[0][0][0] = true;
        dp[0][1][boxes[0] % class_size] = true;
        take[0][1][boxes[0] % class_size] = true;
        for (int j = 1; j < (int) boxes.size(); j++) {
            for (int sz = 0; sz <= class_size; sz++) {
                for (int r = 0; r < class_size; r++) {
                    dp[j][sz][r] = dp[j - 1][sz][r];
                    if (sz > 0 && dp[j - 1][sz - 1][(class_size + r - boxes[j] % class_size) % class_size]) {
                        dp[j][sz][r] = true;
                        take[j][sz][r] = true;
                    } else {
                        take[j][sz][r] = false;
                    }
                }
            }
        }
        vector<bool> used(2 * class_size - 1);
        int sz = class_size, r = 0;
        for (int j = (int) boxes.size() - 1; j >= 0; j--) {
            if (take[j][sz][r]) {
                used[j] = true;
                sz--;
                r += (class_size - boxes[j] % class_size);
                r %= class_size;
            } else {
                used[j] = false;
            }
        }
        vector<int> to_class;
        for (int j = 0; j < (int) boxes.size(); j++) {
            if (!used[j]) {
                a.pb(boxes[j]);
            } else {
                to_class.pb(boxes[j]);
            }
        }
        ans[s2[i].second] = to_class;
    }
 
    int sum = 0;
    for (auto x : a) {
        sum += x;
        sum %= (int) (a.size() + 1);
    }
    int add = (int) (a.size() + 1) - sum;
    ans[s2[k - 1].second] = a;
    ans[s2[k - 1].second].pb(add);
 
    cout << add << '\n';
    for (auto arr : ans) {
        for (auto x : arr) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}

• Didnt solve
• Good problem
• Average problem
• Bad problem

145468383

q = int(input())

for _ in range(q):
    n, k = map(int, input().split())
    s = input()
    if s == s[::-1] or k == 0:
        print(1)
    else:
        print(2)

• Didn't solve
• Good problem
• Average problem
• Bad problem

145468445

def main():
    n, x, y = map(int, input().split())
    a = list(map(int, input().split()))
    if (sum(a) + x + y) % 2 == 0:
        print('Alice')
    else:
        print('Bob')


for _ in range(int(input())):
    main()

• Didn't solve
• Good problem
• Average problem
• Bad problem

145468509

def solve():
    n, k = map(int, input().split())
    if k == 1:
        print("YES")
        for i in range(1, n + 1):
            print(i)
        return

    if n % 2 == 1:
        print("NO")
        return

    print("YES")
    for i in range(1, n + 1):
        print(*[i for i in range(i, n * k + 1, n)])


for _ in range(int(input())):
    solve()

• Didn't solve
• Good problem
• Average problem
• Bad problem

145469065

#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
 
using namespace std;
 
 
int get(const vector <int>& x) {
    cout << "? " << x[0] + 1 << " " << x[1] + 1 << " " << x[2] + 1 << endl;
    int ans;
    cin >> ans;
    return ans;
}
 
 
signed main() {
    ios_base::sync_with_stdio();
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while(t --> 0) {
        int n;
        cin >> n;
    
        pair <int, int> possible = {0, 1};
        for (int i = 2; i < n - 1; i += 2) {
            vector <pair <int, int>> ch(4);
            vector <int> now = {possible.first, possible.second, i, i + 1};
            for (int j = 0; j < 4; j++) {
                vector <int> x = now;
                x.erase(x.begin() + j);
                ch[j] = {get(x), now[j]};
            }
            sort(all(ch));
            possible = {ch[0].second, ch[1].second};
        }
        if (n % 2 == 1) {
            int other = 0;
            while (possible.first == other || possible.second == other) {
                other++;
            }
            vector <pair <int, int>> ch(4);
            vector <int> now = {possible.first, possible.second, n - 1, other};
            for (int j = 0; j < 4; j++) {
                vector <int> x = now;
                x.erase(x.begin() + j);
                ch[j] = {get(x), now[j]};
            }
            sort(all(ch));
            possible = {ch[0].second, ch[1].second};
        }
        cout << "! " << possible.first + 1 << " " << possible.second + 1 << endl;
    }
 
    return 0;
}

• Didn't solve
• Good problem
• Average problem
• Bad problem

145468656

#include <bits/stdc++.h>

#define len(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"

using namespace std;

const int N = 4e5 + 100, H = 2e5 + 50;
vector <pair <int, int>> g[N];
string ans[N];
int pos[N];


void dfs(int v) {
    if (pos[v] == 0) {
        ans[v] = string(len(g[v]), 'L');
    }

    while (pos[v] < len(g[v])) {
        auto [i, ind] = g[v][pos[v]];
        if (i == -1) {
            pos[v]++;
            continue;
        }
        g[i][ind].first = -1, g[v][pos[v]].first = -1;
        if (v < H) {
            ans[v][pos[v]] = 'R';
        }
        pos[v]++;
        dfs(i);
    }
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m;
    map <int, int> ind, cnt;
    int fre_ind = 0;

    vector <vector <int>> nums(m);
    for (int i = 0; i < m; i++) {
        int n;
        cin >> n;
        for (int _ = 0; _ < n; _++) {
            int x;
            cin >> x;
            if (!ind.count(x)) {
                ind[x] = fre_ind++;
            }
            x = ind[x];
            cnt[x]++;
            nums[i].push_back(x);
            g[i].emplace_back(x + H, len(g[x + H]));
            g[x + H].emplace_back(i, len(g[i]) - 1);
        }
    }

    for (auto [num, cn] : cnt) {
        if (cn % 2 == 1) {
            cout << "NO" << endl;
            return 0;
        }
    }

    for (int i = 0; i < N; i++) {
        dfs(i);
    }

    cout << "YES" << endl;
    for (int i = 0; i < m; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

• Didn't solve
• Good problem
• Average problem
• Bad problem

145468716

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
#define endl "\n"
#define int long long

using namespace std;

const int N = 3e5 + 100;
int MOD;
int fib[N];

vector <int> unfib;
int notzero = 0;

void upd(int ind, int delta) {
  notzero -= (unfib[ind] != 0);
  unfib[ind] += delta;
  if (unfib[ind] >= MOD) {
    unfib[ind] -= MOD;
  };
  notzero += (unfib[ind] != 0);
}


signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n, q;
  cin >> n >> q >> MOD;

  fib[0] = fib[1] = 1;
  for (int i = 2; i < N; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  }

  vector <int> delta(n);
  for (int& i : delta) {
    cin >> i;
  }
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    delta[i] = (delta[i] - x + MOD) % MOD;
  }

  unfib.resize(n);
  unfib[0] = delta[0];
  if (len(unfib) >= 2) {
    unfib[1] = (delta[1] - delta[0] + MOD) % MOD;
  }
  for (int i = 2; i < n; i++) {
    unfib[i] = ((long long) delta[i] - delta[i - 1] - delta[i - 2] + MOD * 2) % MOD;
  }
  for (int i = 0; i < n; i++) {
    notzero += (unfib[i] != 0);
  }

  while (q--) {
    char c;
    int l, r;
    cin >> c >> l >> r;
    if (c == 'A') {
      upd(l - 1, 1);
      if (r != n) {
        upd(r, MOD - fib[r - l + 1]);
      }
      if (r < n - 1) {
        upd(r + 1, MOD - fib[r - l]);
      }
    } else {
      upd(l - 1, MOD - 1);
      if (r != n) {
        upd(r, fib[r - l + 1]);
      }
      if (r < n - 1) {
        upd(r + 1, fib[r - l]);
      }
    }
    if (!notzero) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
  return 0;
}

• Didn't solve
• Good problem
• Average problem
• Bad problem