| 1 |
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int tt; cin >> tt; while (tt--) { int a, b, n; cin >> a >> b >> n; n %= 3; if (n == 0) cout << a << ' '; else if (n == 1) cout << b << ' '; else cout << (a ^ b) << ' '; |
| 2 |
using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> b = a; sort(b.begin(), b.end()); b.resize(unique(b.begin(), b.end()) - b.begin()); |
| 3 |
if ((int) b.size() == n) { cout << 0 << ' '; return 0; } for (int i = 0; i < n; i++) { a[i] = (int) (lower_bound(b.begin(), b.end(), a[i]) - b.begin()); } int ans = 0; vector<int> mark(n, 0); for (int i = 0; i < n; i++) { int take = 0; for (int j = 0; j < n; j++) { |
| 4 |
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<vector<int>> a(n, vector<int>(n)); int x = 0; for (int i = 0; i < n; i += 4) { for (int j = 0; j < n; j += 4) { for (int ii = 0; ii < 4; ii++) { |
| 5 |
#include <bits/stdc++.h> using namespace std; template <typename T> class fenwick { public: vector<T> fenw; int n; fenwick(int _n) : n(_n) { fenw.resize(n); } void modify(int x, T v) { while (x < n) { fenw[x] += v; x |= (x + 1); } } T get(int x) { |
| 6 |
T v{}; while (x >= 0) { v += fenw[x]; x = (x & (x + 1)) - 1; } return v; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<long long> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } fenwick<long long> fenw(n); for (int i = 0; i < n; i++) { |
| 7 |
fenw.modify(i, i + 1); } vector<int> a(n); for (int i = n - 1; i >= 0; i--) { int low = 0, high = n - 1; while (low < high) { int mid = (low + high) >> 1; if (fenw.get(mid) > s[i]) { high = mid; } else { low = mid + 1; } } a[i] = low + 1; fenw.modify(low, -low - 1); |
| 8 |
#include <bits/stdc++.h> using namespace std; template <typename T, class F = function<T(const T&, const T&)>> class SparseTable { public: int n; vector<vector<T>> mat; F func; SparseTable(const vector<T>& a, const F& f) : func(f) { n = static_cast<int>(a.size()); |
| 9 |
int max_log = 32 - __builtin_clz(n); mat.resize(max_log); mat[0] = a; for (int j = 1; j < max_log; j++) { mat[j].resize(n - (1 << j) + 1); for (int i = 0; i <= n - (1 << j); i++) { mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]); } } } |
| 10 |
T get(int from, int to) const { assert(0 <= from && from <= to && to <= n - 1); int lg = 32 - __builtin_clz(to - from + 1) - 1; return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int cnt, w; |
| 11 |
cin >> cnt >> w; vector<long long> res(w + 1); while (cnt--) { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } SparseTable<int> st(a, [&](int i, int j) { return max(i, j); }); for (int i = 0; i < w; i++) { int from = max(i - (w - n), 0); |
| 12 |
int to = min(i, n - 1); int cur = st.get(from, to); if (cur < 0 && (i >= n || i < w - n)) { cur = 0; } res[i] += cur; if (from == 0 && to == n - 1 && i >= n && w >= 2 * n + 1) { i = max(i, w - n - 1); } res[i + 1] -= cur; } } for (int i = 0; i < w; i++) { |
| 13 |
using namespace std; const int BITS = 21; const int MAX = (1 << BITS); int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<pair<int, int>> bests(MAX, make_pair(-1, -1)); |
| 14 |
auto Update = [&](pair<int, int>& p, int v) { if (v > p.first) { p.second = p.first; p.first = v; } else { p.second = max(p.second, v); } }; for (int i = 0; i < n; i++) { Update(bests[a[i]], i); } for (int j = 0; j < BITS; j++) { for (int i = 0; i < MAX; i++) { |
| 15 |
if (i & (1 << j)) { Update(bests[i ^ (1 << j)], bests[i].first); Update(bests[i ^ (1 << j)], bests[i].second); } } } auto Can = [&](int num, int high) { for (int i = 0; i < n; i++) { int x = (a[i] ^ num) & high; if (bests[x].second > i) { return true; |
| 16 |
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; long long ans = (long long) 9e18; for (int take2 = 0; take2 < 2; take2++) { vector<int> phi(n + 1); for (int i = 1; i <= n; i++) { |
| 17 |
phi[i] = i; } for (int i = 1; i <= n; i++) { for (int j = i + i; j <= n; j += i) { phi[j] -= phi[i]; } } if (!take2) { for (int i = 4; i <= n; i += 2) { phi[i] = (int) 1e9; } } sort(phi.begin() + 3, phi.end()); long long cur = 1 + take2; for (int i = 3; i <= k + 2; i++) { |
| 18 |
#include <bits/stdc++.h> using namespace std; template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> |
| 19 |
string to_string(tuple<A, B, C, D> p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector<bool> v) { |
| 20 |
bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) { string res = ""; |
| 21 |
for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); |
| 22 |
} res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; |
| 23 |
} template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << endl; } |
| 24 |
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif |
| 25 |
const int N = 100010; int from_leaves[N]; int from_others[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<vector<int>> g(n); for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; --x; --y; g[x].push_back(y); |
| 26 |
g[y].push_back(x); } vector<int> color(n); for (int i = 0; i < n; i++) { cin >> color[i]; } vector<int> order; vector<int> pos(n, -1); vector<int> endd(n, -1); vector<bool> is_leaf(n, false); vector<int> map_to(n); vector<int> deg(n); vector<int> parent(n, -1); |
| 27 |
iota(map_to.begin(), map_to.end(), 0); function<void(int, int)> Dfs = [&](int v, int pv) { parent[v] = pv; deg[v] = (int) g[v].size() - (pv != -1); if (pv != -1 && deg[v] == 1 && deg[pv] == 1) { map_to[v] = map_to[pv]; for (int u : g[v]) { if (u == pv) { |
| 28 |
continue; } Dfs(u, v); } return; } pos[v] = (int) order.size(); order.push_back(v); for (int u : g[v]) { if (u == pv) { continue; } Dfs(u, v); } endd[v] = (int) order.size() - 1; if (deg[v] == 0) { is_leaf[v] = true; order.pop_back(); pos[v] = endd[v] = -1; |
| 29 |
} }; Dfs(0, -1); int cnt = (int) order.size(); memset(from_leaves, 0, sizeof(int) * cnt); memset(from_others, 0, sizeof(int) * cnt); for (int i = 0; i < n; i++) { if (is_leaf[i]) { from_leaves[pos[map_to[parent[i]]]] += (color[i] == 1 ? 1 : -1); } } vector<int> go_to(cnt); |
| 30 |
for (int i = 1; i < cnt; i++) { go_to[i] = pos[map_to[parent[order[i]]]]; } int tt; cin >> tt; vector<int> op(tt), ver(tt), val(tt), res(tt, -1); for (int i = 0; i < tt; i++) { cin >> op[i]; if (op[i] == 1) { cin >> ver[i]; --ver[i]; } if (op[i] == 2) { |
| 31 |
cin >> ver[i] >> val[i]; --ver[i]; } if (op[i] == 3) { cin >> val[i]; } } map<int, int> mp; int beg = 0; while (beg < tt) { int end = beg; while (end + 1 < tt && op[end + 1] == op[end]) { ++end; } if (op[beg] == 1) { mp.clear(); for (int i = beg; i <= end; i++) { |
| 32 |
int v = ver[i]; if (!is_leaf[v]) { v = map_to[v]; from_others[pos[v]] = 0; mp[pos[v] + 1] += 1; mp[endd[v] + 1] -= 1; } } vector<pair<int, int>> segs; int balance = 0; int start = -1; for (auto& p : mp) { if (p.second == 0) { continue; } if (balance == 0) { |
| 33 |
start = p.first; } balance += p.second; if (balance == 0) { segs.emplace_back(start, p.first - 1); start = -1; } } for (auto& p : segs) { int from = p.first; int to = p.second; memset(from_others + from, 0, sizeof(int) * (to - from + 1)); for (int i = to; i >= from; i--) { |
| 34 |
from_others[go_to[i]] += (from_others[i] + from_leaves[i] >= k ? 1 : -1); } } for (int i = beg; i <= end; i++) { int v = ver[i]; if (is_leaf[v]) { res[i] = color[v]; } else { v = map_to[v]; res[i] = (from_others[pos[v]] + from_leaves[pos[v]] >= k); } |
| 35 |
} } if (op[beg] == 2) { for (int i = beg; i <= end; i++) { int v = ver[i]; from_leaves[pos[map_to[parent[v]]]] -= (color[v] == 1 ? 1 : -1); color[v] = val[i]; from_leaves[pos[map_to[parent[v]]]] += (color[v] == 1 ? 1 : -1); } } if (op[beg] == 3) { k = val[end]; |
| 36 |
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, sz; cin >> n >> sz; sz *= 8; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); int k = sz / n; int values = (k < 30 ? (1 << k) : n); |
| 37 |
int ans = 0; int r = 0; int diff = 0; for (int i = 0; i < n; i++) { while (r < n) { if (r > i && a[r] == a[r - 1]) { ++r; } else { if (diff == values) { break; } ++diff; ++r; } } ans = max(ans, r - i); if (i < n - 1 && (i + 1 == r || a[i] != a[i + 1])) { |
| 38 |
#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); for (int i = 0; i < n; i++) { cin >> a[i]; } int tt; cin >> tt; vector<int> op(tt); vector<int> who(tt); vector<int> val(tt); |
| 39 |
for (int i = 0; i < tt; i++) { cin >> op[i]; if (op[i] == 1) { cin >> who[i] >> val[i]; --who[i]; } else { cin >> val[i]; } } vector<int> res(n, -1); int mx = -1; for (int i = tt - 1; i >= 0; i--) { if (op[i] == 1) { if (res[who[i]] == -1) { res[who[i]] = max(val[i], mx); |
| 40 |
#include <bits/stdc++.h> using namespace std; const int N = 55; int dp[N][N][N][N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<string> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } vector<vector<int>> f(n + 1, vector<int>(n + 1, 0)); |
| 41 |
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { f[i + 1][j + 1] = f[i + 1][j] + f[i][j + 1] - f[i][j] + (s[i][j] == '#'); } } auto Get = [&](int xa, int ya, int xb, int yb) { return f[xb + 1][yb + 1] - f[xa][yb + 1] - f[xb + 1][ya] + f[xa][ya]; |
| 42 |
}; for (int i = n - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { for (int ii = i; ii < n; ii++) { for (int jj = j; jj < n; jj++) { if (Get(i, j, ii, jj) == 0) { dp[i][j][ii][jj] = 0; continue; } int res = max(ii - i + 1, jj - j + 1); for (int k = i; k < ii; k++) { |
| 43 |
#include <bits/stdc++.h> using namespace std; template <typename T> class flow_graph { public: static constexpr T eps = (T) 1e-9; struct edge { int from; int to; T c; T f; }; vector<vector<int>> g; vector<edge> edges; int n; int st; int fin; T flow; |
| 44 |
flow_graph(int _n, int _st, int _fin) : n(_n), st(_st), fin(_fin) { assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin); g.resize(n); flow = 0; } void clear_flow() { for (const edge &e : edges) { e.f = 0; } flow = 0; } int add(int from, int to, T forward_cap, T backward_cap) { |
| 45 |
assert(0 <= from && from < n && 0 <= to && to < n); int id = (int) edges.size(); g[from].push_back(id); edges.push_back({from, to, forward_cap, 0}); g[to].push_back(id + 1); edges.push_back({to, from, backward_cap, 0}); return id; } }; template <typename T> |
| 46 |
class dinic { public: flow_graph<T> &g; vector<int> ptr; vector<int> d; vector<int> q; dinic(flow_graph<T> &_g) : g(_g) { ptr.resize(g.n); d.resize(g.n); q.resize(g.n); } bool expath() { fill(d.begin(), d.end(), -1); q[0] = g.fin; d[g.fin] = 0; int beg = 0, end = 1; |
| 47 |
while (beg < end) { int i = q[beg++]; for (int id : g.g[i]) { const auto &e = g.edges[id]; const auto &back = g.edges[id ^ 1]; if (back.c - back.f > g.eps && d[e.to] == -1) { d[e.to] = d[i] + 1; if (e.to == g.st) { return true; } q[end++] = e.to; } } |
| 48 |
} return false; } T dfs(int v, T w) { if (v == g.fin) { return w; } int &j = ptr[v]; while (j >= 0) { int id = g.g[v][j]; const auto &e = g.edges[id]; if (e.c - e.f > g.eps && d[e.to] == d[v] - 1) { T t = dfs(e.to, min(e.c - e.f, w)); if (t > g.eps) { |
| 49 |
g.edges[id].f += t; g.edges[id ^ 1].f -= t; return t; } } j--; } return 0; } T max_flow() { while (expath()) { for (int i = 0; i < g.n; i++) { ptr[i] = (int) g.g[i].size() - 1; } T big_add = 0; while (true) { T add = dfs(g.st, numeric_limits<T>::max()); |
| 50 |
if (add <= g.eps) { break; } big_add += add; } if (big_add <= g.eps) { break; } g.flow += big_add; } return g.flow; } vector<bool> min_cut() { max_flow(); vector<bool> ret(g.n); for (int i = 0; i < g.n; i++) { ret[i] = (d[i] != -1); } return ret; } }; |
| 51 |
int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> xa(m), ya(m), xb(m), yb(m); vector<int> xs = {0, n}; vector<int> ys = {0, n}; for (int i = 0; i < m; i++) { cin >> xa[i] >> ya[i] >> xb[i] >> yb[i]; --xa[i]; --ya[i]; |
| 52 |
xs.push_back(xa[i]); ys.push_back(ya[i]); xs.push_back(xb[i]); ys.push_back(yb[i]); } sort(xs.begin(), xs.end()); xs.resize(unique(xs.begin(), xs.end()) - xs.begin()); sort(ys.begin(), ys.end()); ys.resize(unique(ys.begin(), ys.end()) - ys.begin()); int nx = (int) xs.size() - 1; |
| 53 |
int ny = (int) ys.size() - 1; const long long inf = (long long) 2e18; flow_graph<long long> g(nx + ny + 2, nx + ny, nx + ny + 1); for (int i = 0; i < nx; i++) { g.add(nx + ny, i, xs[i + 1] - xs[i], 0); } for (int i = 0; i < ny; i++) { g.add(nx + i, nx + ny + 1, ys[i + 1] - ys[i], 0); |
| 54 |
} for (int i = 0; i < nx; i++) { for (int j = 0; j < ny; j++) { int ok = 0; for (int k = 0; k < m; k++) { if (xa[k] <= xs[i] && xs[i + 1] <= xb[k] && ya[k] <= ys[j] && ys[j + 1] <= yb[k]) { ok = 1; break; } } if (ok) { g.add(i, nx + j, inf, 0); } } } |
| 55 |
#include <bits/stdc++.h> using namespace std; namespace factorizer { vector<int> least = {0, 1}; vector<int> primes; int precalculated = 1; void RunLinearSieve(int n) { n = max(n, 1); least.assign(n + 1, 0); primes.clear(); for (int i = 2; i <= n; i++) { |
| 56 |
if (least[i] == 0) { least[i] = i; primes.push_back(i); } for (int x : primes) { if (x > least[i] || i * x > n) { break; } least[i * x] = x; } } precalculated = n; } void RunSieve(int n) { RunLinearSieve(n); } template <typename T> vector<pair<T, int>> Factorize(T x) { |
| 57 |
vector<pair<T, int>> ret; for (T i : primes) { T t = x / i; if (i > t) { break; } if (x == t * i) { int cnt = 0; while (x % i == 0) { x /= i; cnt++; } ret.emplace_back(i, cnt); } } if (x > 1) { ret.emplace_back(x, 1); } return ret; } } // namespace factorizer |
| 58 |
vector<int> GetFirsts(const vector<pair<int, int>>& a) { vector<int> b; for (auto& p : a) { b.push_back(p.first); } return b; } mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); const int N = 100010; const int MX = 555; |
| 59 |
int delta[N][2]; int nxt[N][23]; int dist[MX * MX]; int pr[MX * MX]; vector<int> here[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<pair<int, int>> aa(n); for (int i = 0; i < n; i++) { cin >> aa[i].first; aa[i].second = i; |
| 60 |
} shuffle(aa.begin(), aa.end(), rng); vector<int> a(n); vector<int> real_id(n); for (int i = 0; i < n; i++) { a[i] = aa[i].first; real_id[i] = aa[i].second; } factorizer::RunSieve(40000); for (int start = 1; start < n; start++) { vector<vector<int>> f = {GetFirsts(factorizer::Factorize(a[0])), GetFirsts(factorizer::Factorize(a[start]))}; |
| 61 |
vector<int> sz = {(int) f[0].size(), (int) f[1].size()}; for (int i = start + 1; i < n; i++) { for (int r = 0; r < 2; r++) { delta[i][r] = 0; for (int j = 0; j < sz[r]; j++) { if (a[i] % f[r][j] == 0) { delta[i][r] |= (1 << j); } } } } for (int j = 0; j < sz[0] + sz[1]; j++) { |
| 62 |
nxt[n][j] = n; } for (int i = n - 1; i >= start + 1; i--) { for (int j = 0; j < sz[0]; j++) { if ((delta[i][0] & (1 << j)) == 0) { nxt[i][j] = i; } else { nxt[i][j] = nxt[i + 1][j]; } } for (int j = 0; j < sz[1]; j++) { if ((delta[i][1] & (1 << j)) == 0) { |
| 63 |
nxt[i][sz[0] + j] = i; } else { nxt[i][sz[0] + j] = nxt[i + 1][sz[0] + j]; } } } for (int i = 0; i <= n; i++) { here[i].clear(); } for (int t = 0; t < (1 << (sz[0] + sz[1])); t++) { dist[t] = n + 1; } int init = (1 << (sz[0] + sz[1])) - 1; dist[init] = start + 1; |
| 64 |
here[start + 1].push_back(init); for (int at = start + 1; at < n; at++) { for (int t : here[at]) { if (dist[t] != at) { continue; } for (int bit = 0; bit < sz[0]; bit++) { if ((t & (1 << bit)) == 0) { continue; } int to = nxt[at][bit]; if (to == n) { |
| 65 |
continue; } int nt = t & (delta[to][0] | (((1 << (sz[0] + sz[1])) - 1) ^ ((1 << sz[0]) - 1))); if (to + 1 < dist[nt]) { dist[nt] = to + 1; pr[nt] = t; here[to + 1].push_back(nt); } } for (int bit = sz[0]; bit < sz[0] + sz[1]; bit++) { if ((t & (1 << bit)) == 0) { |
| 66 |
continue; } int to = nxt[at][bit]; if (to == n) { continue; } int nt = t & ((delta[to][1] << sz[0]) | ((1 << sz[0]) - 1)); if (to + 1 < dist[nt]) { dist[nt] = to + 1; pr[nt] = ~t; here[to + 1].push_back(nt); } } } } if (dist[0] <= n) { cout << "YES" << ' '; |
| 67 |
vector<int> res(n); for (int i = 0; i < start; i++) { res[real_id[i]] = 1; } res[real_id[start]] = 2; int t = 0; while (t != init) { int id = real_id[dist[t] - 1]; if (pr[t] >= 0) { res[id] = 1; t = pr[t]; } else { res[id] = 2; t = ~pr[t]; } } for (int i = 0; i < n; i++) { |
| 68 |
if (res[i] == 0) { res[i] = rng() % 2 + 1; } } for (int i = 0; i < n; i++) { if (i > 0) { cout << " "; } cout << res[i]; } cout << ' '; return 0; } if (__gcd(a[0], a[start]) == a[0]) { break; } a[0] = __gcd(a[0], a[start]); } cout << "NO" << ' '; return 0; |
| 69 |
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m, ta, tb, k; cin >> n >> m >> ta >> tb >> k; 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++) { |
| 70 |
cin >> b[i]; } if (k >= min(n, m)) { cout << -1 << ' '; return 0; } int ans = 0; for (int x = 0; x <= k; x++) { int at_b = a[x] + ta; int pos = (int) (lower_bound(b.begin(), b.end(), at_b) - b.begin()); pos += (k - x); if (pos >= m) { cout << -1 << ' '; |
| 71 |
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m, ta, tb, k; cin >> n >> m >> ta >> tb >> k; 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++) { |
| 72 |
cin >> b[i]; } if (k >= min(n, m)) { cout << -1 << ' '; return 0; } int ans = 0; for (int x = 0; x <= k; x++) { int at_b = a[x] + ta; int pos = (int) (lower_bound(b.begin(), b.end(), at_b) - b.begin()); pos += (k - x); if (pos >= m) { cout << -1 << ' '; |
| 73 |
#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); for (int i = 0; i < n; i++) { cin >> a[i]; a[i]--; } vector<pair<int, int>> ret; { int i = 0, j = n - 1; while (i < n / 2) { |
| 74 |
while (i < n / 2 && a[i] < n / 2) { ++i; } while (j >= n / 2 && a[j] >= n / 2) { --j; } if (i < n / 2 && j >= n / 2) { if (j - i >= n / 2) { ret.emplace_back(i, j); } else { ret.emplace_back(i, n - 1); ret.emplace_back(0, n - 1); ret.emplace_back(0, j); |
| 75 |
ret.emplace_back(0, n - 1); ret.emplace_back(i, n - 1); } swap(a[i], a[j]); } } } vector<int> pos(n); for (int i = 0; i < n; i++) { pos[a[i]] = i; } for (int i = 0; i < n / 2; i++) { if (pos[i] != i) { int j = pos[i]; ret.emplace_back(i, n - 1); ret.emplace_back(j, n - 1); |
| 76 |
ret.emplace_back(i, n - 1); swap(a[i], a[j]); pos[a[i]] = i; pos[a[j]] = j; } } for (int i = n / 2; i < n; i++) { if (pos[i] != i) { int j = pos[i]; ret.emplace_back(0, i); ret.emplace_back(0, j); ret.emplace_back(0, i); swap(a[i], a[j]); pos[a[i]] = i; |
| 77 |
#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); vector<int> b(n); vector<int> lt; vector<int> gt; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; if (a[i] < b[i]) { |
| 78 |
lt.push_back(i); } else { gt.push_back(i); } } vector<int> ans; if (lt.size() > gt.size()) { sort(lt.begin(), lt.end(), [&](int i, int j) { return b[i] > b[j]; }); ans = lt; } else { sort(gt.begin(), gt.end(), [&](int i, int j) { return a[i] < a[j]; }); |
| 79 |
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<pair<int, int>> a(n); vector<int> b(n); for (int i = 0; i < n; i++) { cin >> a[i].first; a[i].second = i; } for (int i = 0; i < n; i++) { |
| 80 |
cin >> b[i]; } sort(a.begin(), a.end()); sort(b.begin(), b.end()); vector<tuple<int, int, int>> ret; vector<pair<int, int>> st; for (int i = 0; i < n; i++) { int diff = b[i] - a[i].first; if (diff > 0) { st.emplace_back(a[i].second, diff); } while (diff < 0) { |
| 81 |
if (st.empty()) { cout << "NO" << " "; return 0; } int take = min(-diff, st.back().second); ret.emplace_back(st.back().first, a[i].second, take); diff += take; st.back().second -= take; if (st.back().second == 0) { st.pop_back(); } } } if (!st.empty()) { |
| 82 |
#include <bits/stdc++.h> using namespace std; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> |
| 83 |
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; |
| 84 |
res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) |
| 85 |
#else #define debug(...) 42 #endif int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<long long> val(n); vector<long long> mask(n); vector<int> when(n); long long total = 0; for (int i = 0; i < n; i++) { cin >> val[i] >> mask[i]; |
| 86 |
total += val[i]; when[i] = __builtin_ctzll(mask[i]); } if (total < 0) { for (int i = 0; i < n; i++) { val[i] *= -1; } total *= -1; } long long s = 0; for (int bit = 62; bit >= 0; bit--) { vector<long long> t(2, 0); for (int i = 0; i < n; i++) { if (when[i] == bit) { |
| 87 |
#include <bits/stdc++.h> using namespace std; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> |
| 88 |
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; |
| 89 |
res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) |
| 90 |
#else #define debug(...) 42 #endif vector<int> least = {0, 1}; vector<int> primes; int precalculated = 1; void RunLinearSieve(int n) { n = max(n, 1); least.assign(n + 1, 0); primes.clear(); for (int i = 2; i <= n; i++) { if (least[i] == 0) { least[i] = i; |
| 91 |
primes.push_back(i); } for (int x : primes) { if (x > least[i] || i * x > n) { break; } least[i * x] = x; } } precalculated = n; } const int N = 100010; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> a(n); |
| 92 |
for (int i = 0; i < n; i++) { cin >> a[i]; } int mx = *max_element(a.begin(), a.end()); RunLinearSieve(mx); vector<int> pid(mx + 1, -1); int pcnt = 0; vector<vector<int>> z(n); for (int i = 0; i < n; i++) { int x = a[i]; int y = 1; int last = -1; while (x > 1) { |
| 93 |
if (least[x] != last) { y *= least[x]; if (pid[least[x]] == -1) { pid[least[x]] = pcnt++; } z[i].push_back(pid[least[x]]); last = least[x]; } x /= least[x]; } a[i] = y; } debug(a); vector<vector<int>> ids(pcnt); for (int i = 0; i < n; i++) { for (int j : z[i]) { |
| 94 |
ids[j].push_back(i); } } vector<bitset<N>> bitsets; vector<int> bitset_id(pcnt, -1); for (int i = 0; i < pcnt; i++) { if ((int) ids[i].size() >= n / 239) { bitset_id[i] = (int) bitsets.size(); bitsets.emplace_back(); for (int j : ids[i]) { bitsets.back()[j] = 1; |
| 95 |
} } } bitset<N> alive; for (int i = 0; i < n; i++) { alive[i] = 1; } vector<char> visited_value(mx + 1, 0); vector<vector<int>> comps; vector<int> alone; for (int st = 0; st < n; st++) { if (alive[st] == 0) { continue; } vector<int> que(1, st); alive[st] = 0; |
| 96 |
for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; if (visited_value[a[i]]) { continue; } visited_value[a[i]] = 1; bitset<N> go = alive; for (int j : z[i]) { if (bitset_id[j] == -1) { for (int u : ids[j]) { go[u] = 0; } } else { go ^= (go & bitsets[bitset_id[j]]); |
| 97 |
} } for (int u = go._Find_first(); u < n; u = go._Find_next(u)) { que.push_back(u); alive[u] = 0; } } debug(que); if (que.size() == 1) { alone.push_back(que[0]); } else { comps.push_back(que); } } vector<int> ret; if ((int) alone.size() + (int) comps.size() >= k) { |
| 98 |
for (auto& c : comps) { alone.push_back(c[0]); } alone.resize(k); ret = alone; } else { vector<int> order(comps.size()); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) { return comps[i].size() > comps[j].size(); |
| 99 |
}); int take = 0; int sum = 0; while (sum < k - 1) { sum += (int) comps[order[take]].size(); take++; } if (sum == k - 1) { comps[order[0]].pop_back(); } for (int i : order) { for (int u : comps[i]) { ret.push_back(u); } } } for (int i = 0; i < k; i++) { |
| 100 |
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int n = (int) s.size(); int cnt = 0; for (char c : s) { cnt += (c == 'a'); } if ((n - cnt) % 2 != 0) { cout << ":(" << ' '; return 0; |
Комментарии