Codeforces Round #693 (Div. 3)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; typedef long long ll; int T, w, h, n; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%d%d", &w, &h, &n); int res = 1; while (0 == w % 2) { res *= 2; w /= 2; } while (0 == h % 2) { res *= 2; h /= 2; } if (res >= n) printf("YES "); else printf("NO "); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; typedef long long ll; int T, n; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); int a = 0, b = 0; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); if (1 == x) a += 1; else b += 1; } if (0 == b % 2 && 0 == a % 2) printf("YES "); else if (0 == b % 2 && 1 == a % 2) printf("NO "); else if (1 == b % 2) { if (0 != a && 0 == a % 2) printf("YES "); else printf("NO "); } } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; typedef long long ll; const int N = 200010; int T, n, a[N], dp[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); dp[i] = 0; } for (int i = 1; i <= n; i++) { if (i + a[i] > n) continue; dp[i + a[i]] = max(dp[i + a[i]], dp[i] + a[i]); } int res = 0; for (int i = 1; i <= n; i++) res = max(res, dp[i] + a[i]); printf("%d ", res); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; typedef long long ll; const int N = 200010; int T, n; ll a[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1); ll ra = 0, rb = 0; for (int i = 1; i <= n; i++) { if (1 == i % 2 && 0 == a[i] % 2) ra += a[i]; if (0 == i % 2 && 1 == a[i] % 2) rb += a[i]; } if (ra > rb) printf("Alice "); else if (ra == rb) printf("Tie "); else printf("Bob "); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; typedef long long ll; const int N = 400010; const int INF = 0x3f3f3f3f; struct node { int w, h, id; node() { } node(int _w, int _h, int _id) : w(_w), h(_h), id(_id) { } }; int T, n, res[N]; node a[N]; vector<node> v; bool cmp(node a, node b) { if (a.h != b.h) return a.h < b.h; return a.w < b.w; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { v.clear(); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i].h, &a[i].w); a[i].id = i; v.push_back(node(a[i].h, a[i].w, i)); v.push_back(node(a[i].w, a[i].h, i)); } sort(a + 1, a + n + 1, cmp); sort(v.begin(), v.end(), cmp); int p = -1, imin = INF, np = -1; for (int i = 1; i <= n; i++) { while (p + 1 < v.size() && v[p + 1].h < a[i].h) { p += 1; if (v[p].w < imin) { imin = v[p].w; np = v[p].id; } } if (imin < a[i].w) res[a[i].id] = np; else res[a[i].id] = -1; } for (int i = 1; i <= n; i++) { printf("%d", res[i]); printf(i == n ? " " : " "); } } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 200010; int T, n, m, r[N], c[N]; map<int, int> mp; vector<pii> vo; bool cmp(pii a, pii b) { return a.second < b.second; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { vo.clear(); mp.clear(); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &r[i], &c[i]); mp[c[i]] += 1; } for (int i = 1; i <= m; i++) { if (0 == mp[c[i]]) continue; if (2 == mp[c[i]]) { vo.push_back( { 3, c[i] } ); mp[c[i]] = 0; } else vo.push_back( { r[i], c[i] } ); } sort(vo.begin(), vo.end(), cmp); int f = 1, t = 0, lst = 0, tlst = 0; for (int i = 0; i < vo.size(); i++) { if (0 == t && 3 == vo[i].first) continue; if (0 == t) { t = 1; lst = vo[i].second; tlst = vo[i].first; } else { if (3 == vo[i].first) { f = 0; break; } int now = vo[i].second, tnow = vo[i].first; if ((0 == (now - lst) % 2 && tnow != tlst) || (1 == (now - lst) % 2 && tnow == tlst)) { t = lst = tlst = 0; } else { f = 0; break; } } } if (0 != t) f = 0; printf(0 == f ? "NO " : "YES "); } return 0; }
Codeforces Round #667 (Div. 3)
A - Yet Another Two Integers Problem
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> using namespace std; typedef long long ll; int T, a, b; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%d", &a, &b); printf("%d ", (abs(a - b) + 9) / 10); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> using namespace std; typedef long long ll; int T; ll a, b, x, y, n; ll solve(ll a, ll b, ll x, ll y, ll n) { ll imin = min(n, a - x); n -= imin; a -= imin; imin = min(n, b - y); n -= imin; b -= imin; return a * b; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%lld%lld%lld%lld%lld", &a, &b, &x, &y, &n); printf("%lld ", min(solve(a, b, x, y, n), solve(b, a, y, x, n))); } return 0; }
C - Yet Another Array Restoration
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> using namespace std; typedef long long ll; int T, n, x, y; vector<int> res; void solve() { res.clear(); scanf("%d%d%d", &n, &x, &y); for (int i = 1; i <= y - x; i++) { if (0 != (y - x) % i) continue; if ((y - x) / i + 1 > n) continue; int cnt = 0; for (int j = x; j <= y && cnt < n; j += i, cnt++) res.push_back(j); for (int j = x - i; j > 0 && cnt < n; j -= i, cnt++) res.push_back(j); for (int j = y + i; cnt < n; j += i, cnt++) res.push_back(j); break; } for (int i = 0; i < res.size(); i++) { printf("%d", res[i]); printf(i == res.size() - 1 ? " " : " "); } } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) solve(); return 0; }
D - Decrease the Sum of Digits
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> using namespace std; typedef long long ll; const int N = 20; const ll INF = 1000000000000000000; int T, s, a[N], b[N]; ll n; void solve() { for (int i = 0; i < N; i++) a[i] = 0; scanf("%lld%d", &n, &s); ll tn = n, res = INF; int cnt = 0, sum = 0; while (tn) { a[++cnt] = tn % 10; sum += a[cnt]; tn /= 10; } if (sum <= s) { printf("0 "); return; } for (int i = 2; i <= cnt + 1; i++) { for (int j = 0; j < N; j++) b[j] = a[j]; if (9 == b[i]) continue; b[i] += 1; for (int j = i - 1; j >= 1; j--) b[j] = 0; int tsum = 0; for (int j = 0; j < N; j++) tsum += b[j]; if (tsum > s) continue; ll now = 0; for (int j = N - 1; j >= 1; j--) now = now * 10 + b[j]; res = min(res, now - n); } printf("%lld ", res); } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) solve(); return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> using namespace std; const int N = 200010; int T, n, k, x[N], y[N], dp[N]; void solve() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &x[i]); for (int i = 1; i <= n; i++) scanf("%d", &y[i]); for (int i = 1; i <= n; i++) dp[i] = 0; sort(x + 1, x + n + 1); int l = 1, imax = 0; for (int i = 1; i <= n; i++) { while (x[i] - x[l] > k) l += 1; dp[i] = max(dp[i - 1], i - l + 1); imax = max(imax, dp[l - 1] + i - l + 1); } printf("%d ", imax); } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) solve(); return 0; }
Codeforces Round #694 (Div. 2)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <string> using namespace std; typedef long long ll; const int N = 100010; int T, n; ll x, a[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%lld", &n, &x); ll imax = 0, imin = 0, sum = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); imax = imax + (a[i] + x - 1) / x; sum += a[i]; } printf("%lld %lld ", (sum + x - 1) / x, imax); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <string> using namespace std; typedef long long ll; const int N = 100010; struct node { ll q, cnt; node() { } node(ll _q, ll _cnt) : q(_q), cnt(_cnt) { } }; int T, n; ll x, a[N]; queue<node> que; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%lld", &n, &x); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); que.push(node(a[i], 1)); } ll res = 0; while (!que.empty()) { node nd = que.front(); if (nd.q % x) break; que.pop(); res += nd.q * nd.cnt; que.push(node(nd.q / x, x * nd.cnt)); } while (!que.empty()) { node nd = que.front(); que.pop(); res += nd.q * nd.cnt; } printf("%lld ", res); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <string> using namespace std; typedef long long ll; const int N = 300010; struct node { int k, id; }; int T, n, m; ll c[N]; node nd[N]; bool cmp(node a, node b) { if (c[a.k] != c[b.k]) return c[a.k] > c[b.k]; return a.id > b.id; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &nd[i].k); nd[i].id = i; } for (int i = 1; i <= m; i++) scanf("%lld", &c[i]); sort(nd + 1, nd + n + 1, cmp); ll res = 0; int p = 1; for (int i = 1; i <= n; i++) { if (p <= m) { if (nd[i].k < p) res += c[nd[i].k]; else { if (c[p] < c[nd[i].k]) { res += c[p]; p += 1; } else res += c[nd[i].k]; } } else res += c[nd[i].k]; } printf("%lld ", res); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 1000010; int T, n, q, tot; int a[N], isp[N], p[N]; unordered_map<int, int> mp; vector<int> v; void init(int n) { for (int i = 2; i <= n; i++) { if (!isp[i]) p[++tot] = i; for (int j = 1; j <= tot && p[j] <= n / i; j++) { isp[i * p[j]] = 1; if (0 == i % p[j]) break; } } } void divide(int n) { int res = 1; for (int i = 1; i <= tot; i++) { int cnt = 0; while (0 == n % p[i]) { n /= p[i]; cnt += 1; } if (1 == cnt % 2) res *= p[i]; if (n < 1ll * p[i] * p[i]) break; } if (n > 1) res *= n; mp[res] += 1; v.push_back(res); } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); init(N - 5); scanf("%d", &T); while (T--) { v.clear(); mp.clear(); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); divide(a[i]); } int r1 = 0, r2 = mp[1]; for (int i = 0; i < v.size(); i++) r1 = max(r1, mp[v[i]]); for (int i = 0; i < v.size(); i++) { if (1 == v[i]) continue; if (0 == mp[v[i]] % 2) { r2 += mp[v[i]]; mp[v[i]] = 0; } } r2 = max(r1, r2); scanf("%d", &q); while (q--) { ll w; scanf("%lld", &w); printf("%d ", w ? r2 : r1); } } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 300010; struct Edge { int to, nex; }; int T, n, m, cnt, head[N], vis[N]; Edge edge[2 * N]; vector<int> v; void init() { cnt = 0; v.clear(); for (int i = 1; i <= n; i++) head[i] = vis[i] = 0; } void add_edge(int u, int v) { edge[++cnt].to = v; edge[cnt].nex = head[u]; head[u] = cnt; } void dfs(int u) { int f = 0; for (int i = head[u]; 0 != i; i = edge[i].nex) { int v = edge[i].to; if (2 == vis[v]) f = 1; } if (1 == f) vis[u] = 1; else vis[u] = 2; for (int i = head[u]; 0 != i; i = edge[i].nex) { int v = edge[i].to; if (vis[v]) continue; dfs(v); } } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); init(); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v); add_edge(v, u); } dfs(1); int cnt = 0; for (int i = 1; i <= n; i++) { if (2 == vis[i]) v.push_back(i); if (vis[i]) cnt++; } if (cnt < n) { printf("NO "); continue; } printf("YES %d ", v.size()); for (int i = 0; i < v.size(); i++) { printf("%d", v[i]); printf(i == v.size() - 1 ? " " : " "); } } return 0; }
Codeforces Round #690 (Div. 3)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int N = 310; int T, n, a[N], res[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int l = 1, r = n; for (int i = 1; i <= n; i++) { if (i & 1) res[i] = a[l++]; else res[i] = a[r--]; } for (int i = 1; i <= n; i++) { printf("%d", res[i]); printf(i == n ? " " : " "); } } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int N = 210; int T, n; char s[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%s", &n, s + 1); int len = strlen(s + 1), ok = 0; if ('2' == s[1] && '0' == s[2] && '2' == s[3] && '0' == s[4]) ok = 1; if ('2' == s[1] && '0' == s[2] && '2' == s[3] && '0' == s[n]) ok = 1; if ('2' == s[1] && '0' == s[2] && '2' == s[n - 1] && '0' == s[n]) ok = 1; if ('2' == s[1] && '0' == s[n - 2] && '2' == s[n - 1] && '0' == s[n]) ok = 1; if ('2' == s[n - 3] && '0' == s[n - 2] && '2' == s[n - 1] && '0' == s[n]) ok = 1; printf(1 == ok ? "YES " : "NO "); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <unordered_map> #include <string> using namespace std; typedef long long ll; int T, n; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); if (n > 45) { printf("-1 "); continue; } int now = 9, res = 0, b = 1; while (n) { int imin = min(now, n); res = res + b * imin; b *= 10; now -= 1; n -= imin; } printf("%d ", res); } return 0; }
D - Add to Neighbour and Remove
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 3010; int T, n, a[N], sum[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = sum[i - 1] + a[i]; } int res = 1; for (int i = 1; i <= n; i++) { int cnt = 1, s = sum[i], p = i + 1, ts = 0, f = 1; while (p <= n) { ts += a[p]; p += 1; if (ts == s) { ts = 0; cnt += 1; } if (ts > s) { f = 0; break; } } if (0 != ts) f = 0; if (f) res = max(res, cnt); } printf("%d ", n - res); } return 0; }
E1 - Close Tuples (easy version)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 200010; const ll mod = 1000000007; int T, n, a[N]; ll C(int n) { return 1ll * n * (n - 1) / 2; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1); if (n < 3) { printf("0 "); continue; } int l = 1; ll res = 0; for (int i = 3; i <= n; i++) { while (a[i] - a[l] > 2) l += 1; if (i - l + 1 < 3) continue; res += C(i - l); } printf("%lld ", res); } return 0; }
E2 - Close Tuples (hard version)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 200010; const ll mod = 1000000007; int T, n, m, k, a[N]; ll fac[N], inv[N]; void init() { fac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod; inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; inv[0] = 1; for (int i = 1; i < N; i++) inv[i] = inv[i] * inv[i - 1] % mod; } ll C(int n, int m) { ll res = fac[n] * inv[m] % mod * inv[n - m] % mod; return res; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); init(); scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1); if (m > n) { printf("0 "); continue; } int l = 1; ll res = 0; for (int i = m; i <= n; i++) { while (a[i] - a[l] > k) l += 1; if (i - l + 1 < m) continue; res = (res + C(i - l, m - 1)) % mod; } printf("%lld ", res); } return 0; }
F - The Treasure of The Segments
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 1000010; int T, n, l[N], r[N], cl[N], cr[N]; vector<int> alls; int get_id(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { alls.clear(); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &l[i], &r[i]); alls.push_back(l[i]); alls.push_back(r[i]); alls.push_back(l[i] - 1); alls.push_back(r[i] + 1); } sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); for (int i = 0; i <= alls.size() + 1; i++) cl[i] = cr[i] = 0; for (int i = 1; i <= n; i++) { cl[get_id(r[i])] += 1; cr[get_id(l[i])] += 1; } for (int i = 1; i <= alls.size(); i++) cl[i] += cl[i - 1]; for (int i = alls.size(); i >= 1; i--) cr[i] += cr[i + 1]; int res = n; for (int i = 1; i <= n; i++) { int idl = get_id(l[i] - 1), idr = get_id(r[i] + 1); res = min(res, cl[idl] + cr[idr]); } printf("%d ", res); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 60; int T, n, a[N]; set<int> st; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { st.clear(); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) { for (int k = i + 1; k <= n; k++) { st.insert(a[k] - a[i]); } } printf("%d ", st.size()); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 1000010; int T, n, c[N], vis[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= 2 * n + 1; i++) c[i] = vis[i] = 0; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); c[x] += 1; } for (int i = 1; i <= 2 * n; i++) { if (0 == c[i]) continue; if (0 == vis[i]) { if (1 == c[i]) vis[i] = 1; else vis[i] = vis[i + 1] = 1; } else vis[i + 1] = 1; } int res = 0; for (int i = 1; i <= 2 * n + 1; i++) res += vis[i]; printf("%d ", res); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 1000010; int T, f[N]; char s[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%s", s + 1); int len = strlen(s + 1), res = 0; for (int i = 1; i <= len; i++) f[i] = 0; for (int i = 1; i <= len; i++) { if (1 == f[i]) continue; if (0 == f[i] && i + 1 <= len && s[i] == s[i + 1]) { res += 1; f[i + 1] = 1; } if (0 == f[i] && i + 2 <= len && s[i] == s[i + 2]) { res += 1; f[i + 2] = 1; } } printf("%d ", res); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 100010; struct node { int id, cnt; ll w; node(int _id, int _cnt, ll _w) : id(_id), cnt(_cnt), w(_w) { } }; int T, n, deg[N]; ll w[N]; vector<node> v; vector<ll> res; bool cmp(node a, node b) { return a.w > b.w; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { res.clear(); v.clear(); scanf("%d", &n); ll sum = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &w[i]); deg[i] = 0; sum += w[i]; } for (int i = 1; i <= n - 1; i++) { int u, v; scanf("%d%d", &u, &v); deg[u] += 1; deg[v] += 1; } for (int i = 1; i <= n; i++) { if (1 == deg[i]) continue; v.push_back(node(i, deg[i], w[i])); } sort(v.begin(), v.end(), cmp); res.push_back(sum); int p = 0; for (int i = 2; i <= n - 1; i++) { while (1 == v[p].cnt) p += 1; sum += v[p].w; res.push_back(sum); v[p].cnt -= 1; } for (int i = 0; i < res.size(); i++) { printf("%lld", res[i]); printf(i == res.size() - 1 ? " " : " "); } } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 500010; const ll mod = 1000000007; int T, n; ll w[N], s[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 0; i <= 60; i++) s[i] = 0; for (int i = 1; i <= n; i++) scanf("%lld", &w[i]); for (int i = 0; i <= 60; i++) { ll base = (1ll << i); for (int k = 1; k <= n; k++) { if (w[k] & base) s[i] = (s[i] + base % mod) % mod; } } ll res = 0; for (int i = 1; i <= n; i++) { ll a = 0, b = 0; for (int k = 0; k <= 60; k++) { ll base = (1ll << k); if (w[i] & base) { a = (a + s[k]) % mod; b = (b + base % mod * n % mod) % mod; } else b = (b + s[k]) % mod; } res = (res + a * b % mod) % mod; } printf("%lld ", res); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 500010; const ll mod = 1000000007; int n, m, fa[N]; vector<int> res; void init() { for (int i = 1; i <= m + 1; i++) fa[i] = i; } int find(int x) { return (fa[x] == x) ? x : (fa[x] = find(fa[x])); } bool nuio(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) { fa[fx] = fy; return true; } return false; } ll power(ll a, ll n) { ll res = 1; while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d%d", &n, &m); init(); for (int i = 1; i <= n; i++) { int k, a, b; scanf("%d%d", &k, &a); if (1 == k) b = m + 1; else scanf("%d", &b); if (nuio(a, b)) res.push_back(i); } printf("%lld %d ", power(2, res.size()), res.size()); for (int i = 0; i < res.size(); i++) { printf("%d", res[i]); printf(i == res.size() - 1 ? " " : " "); } return 0; }
Codeforces Round #634 (Div. 3)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; int T, n; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); printf("%d ", 0 == n % 2 ? n / 2 - 1 : n / 2); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; int T, n, a, b; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &a, &b); for (int i = 0; i < n; i++) printf("%c", char('a' + i % b)); printf(" "); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 200010; int T, n, c[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) c[i] = 0; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); c[x] += 1; } int imax = 0, cnt = 0; for (int i = 1; i <= n; i++) { if (0 == c[i]) continue; imax = max(imax, c[i]); cnt += 1; } if (imax < cnt) printf("%d ", imax); else if (imax == cnt) printf("%d ", cnt - 1); else printf("%d ", cnt); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 110; int T; char c[N][N]; void change(int x, int y) { int now = c[x][y] - '0'; if (9 == now) now = 1; else now = now + 1; c[x][y] = char(now + '0'); } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { for (int i = 1; i <= 9; i++) scanf("%s", c[i] + 1); change(1, 1); change(2, 4); change(3, 7); change(4, 2); change(5, 5); change(6, 8); change(7, 3); change(8, 6); change(9, 9); for (int i = 1; i <= 9; i++) printf("%s ", c[i] + 1); } return 0; }
E1 - Three Blocks Palindrome (easy version)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 200010; const int M = 210; int T, n, a[N], b[M][N], bn[M], c[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= 200; i++) bn[i] = 0; for (int i = n; i >= 1; i--) { bn[a[i]] += 1; b[a[i]][bn[a[i]]] = i; } int res = 0; for (int i = 1; i <= 200; i++) res = max(res, bn[i]); for (int i = 1; i <= 200; i++) { for (int j = 1; j <= n; j++) { if (a[j] == i) c[j] = c[j - 1] + 1; else c[j] = c[j - 1]; } for (int j = 1; j <= 200; j++) { for (int k = 1; 2 * k <= bn[j]; k++) { int l = b[j][bn[j] - k + 1] + 1, r = b[j][k] - 1; res = max(res, 2 * k + c[r] - c[l - 1]); } } } printf("%d ", res); } return 0; }
E2 - Three Blocks Palindrome (hard version)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 200010; const int M = 210; int T, n, a[N], b[M][N], bn[M], c[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= 200; i++) bn[i] = 0; for (int i = n; i >= 1; i--) { bn[a[i]] += 1; b[a[i]][bn[a[i]]] = i; } int res = 0; for (int i = 1; i <= 200; i++) res = max(res, bn[i]); for (int i = 1; i <= 200; i++) { for (int j = 1; j <= n; j++) { if (a[j] == i) c[j] = c[j - 1] + 1; else c[j] = c[j - 1]; } for (int j = 1; j <= 200; j++) { for (int k = 1; 2 * k <= bn[j]; k++) { int l = b[j][bn[j] - k + 1] + 1, r = b[j][k] - 1; res = max(res, 2 * k + c[r] - c[l - 1]); } } } printf("%d ", res); } return 0; }
Educational Codeforces Round 101 (Rated for Div. 2)
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <stack> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 110; int T; char s[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%s", s + 1); int len = strlen(s + 1), l = 0, r = 0; for (int i = 1; i <= len; i++) { if ('(' == s[i]) l = i; if (')' == s[i]) r = i; } if (1 == (len - 2) % 2) { printf("NO "); continue; } if (l < r || (l < len && r > 1)) { printf("YES "); continue; } printf("NO "); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <stack> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 110; int T, n, m, a[N], b[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d", &n); int maxa = 0, maxb = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); a[i] += a[i - 1]; maxa = max(maxa, a[i]); } scanf("%d", &m); for (int i = 1; i <= m; i++) { scanf("%d", &b[i]); b[i] += b[i - 1]; maxb = max(maxb, b[i]); } printf("%d ", maxa + maxb); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <map> #include <set> #include <stack> #include <unordered_map> #include <string> using namespace std; typedef long long ll; const int N = 200010; int T, n; ll k, h[N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d%lld", &n, &k); for (int i = 1; i <= n; i++) scanf("%lld", &h[i]); ll l = h[1], r = h[1]; int f = 1; for (int i = 2; i <= n; i++) { r = min(h[i] + k - 1, r + k - 1); l = max(h[i], l - k + 1); if (r >= l) continue; f = 0; break; } if (1 == f && h[n] == l) printf("YES "); else printf("NO "); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cmath> #include <map> #include <set> #include <stack> #include <unordered_map> #include <string> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 200010; int T, n; vector<pii> v; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { v.clear(); scanf("%d", &n); int t = n; while (true) { if (t <= 2) break; int x = int(sqrt(t)); if (x * x < t) x += 1; for (int i = x + 1; i < t; i++) v.push_back( { i, t } ); v.push_back( { t, x } ); v.push_back( { t, x } ); t = x; } printf("%d ", v.size()); for (int i = 0; i < v.size(); i++) printf("%d %d ", v[i].first, v[i].second); } return 0; }
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cmath> #include <map> #include <set> #include <stack> #include <unordered_map> #include <string> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 1000010; const int M = 20; int T, n, k, cnt, sum[N]; unordered_map<int, int> mp; char s[N], res[N]; void Hash(int l, int r) { int res = 0; for (int i = l; i <= r; i++) res = res * 2 + s[i] - '0'; mp[res] = 1; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &T); while (T--) { mp.clear(); cnt = 0; scanf("%d%d%s", &n, &k, s + 1); for (int i = 1; i <= n; i++) s[i] = char(2 * '0' - s[i] + 1); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + s[i] - '0'; for (int i = 1; i + k - 1 <= n; i++) { if (k > M && sum[i + k - 1 - M] - sum[i - 1] >= 1) continue; if (k <= M) Hash(i, i + k - 1); else Hash(i + k - M, i + k - 1); } for (int i = 0; i < (1 << min(M, k)); i++) { if (mp[i]) continue; for (int j = 0; j < max(k - M, 0); j++) res[++cnt] = '0'; for (int j = min(k, M) - 1; j >= 0; j--) { if ((i >> j) & 1) res[++cnt] = '1'; else res[++cnt] = '0'; } break; } res[cnt + 1] = '