Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
string s1, s2;
cin >> s1 >> s2;
s1 += s2;
cout << set<char>(s1.begin(), s1.end()).size() - 1 << endl;
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n, m, sx, sy, d = map(int, input().split())
if min(sx - 1, m - sy) <= d and min(n - sx, sy - 1) <= d:
print(-1)
else:
print(n + m - 2)
1721C - Min-Max Array Transformation
Идея: BledDest
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(' ').map { it.toInt() }
val b = readLine()!!.split(' ').map { it.toInt() }
val indices = (0 until n).sortedBy { a[it] }
val mn = Array(n) { 0 }
val mx = Array(n) { 0 }
var lst = n
for (i in n - 1 downTo 0) {
val pos = indices[i]
mn[pos] = lowerBound(b, a[pos])
mx[pos] = lst - 1;
if (i == mn[pos])
lst = i
mn[pos] = b[mn[pos]] - a[pos]
mx[pos] = b[mx[pos]] - a[pos]
}
println(mn.joinToString(" "))
println(mx.joinToString(" "))
}
}
fun lowerBound(a: List<Int>, v: Int): Int {
var l = -1; var r = a.size
while (r - l > 1) {
val m = (l + r) / 2
if (a[m] < v)
l = m
else
r = m
}
return r
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int& x : a) cin >> x;
for (int& x : b) cin >> x;
auto check = [&](int ans) {
map<int, int> cnt;
for (int x : a) ++cnt[x & ans];
for (int x : b) --cnt[~x & ans];
bool ok = true;
for (auto it : cnt) ok &= it.second == 0;
return ok;
};
int ans = 0;
for (int bit = 29; bit >= 0; --bit)
if (check(ans | (1 << bit)))
ans |= 1 << bit;
cout << ans << '\n';
}
}
1721E - Prefix Function Queries
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int AL = 26;
vector<int> prefix_function(const string &s){
int n = s.size();
vector<int> p(n);
for (int i = 1; i < n; ++i){
int k = p[i - 1];
while (k > 0 && s[i] != s[k])
k = p[k - 1];
k += (s[i] == s[k]);
p[i] = k;
}
return p;
}
int main() {
cin.tie(0);
iostream::sync_with_stdio(false);
string s;
cin >> s;
int n = s.size();
auto p = prefix_function(s);
vector<vector<int>> A(n, vector<int>(AL));
forn(i, n) forn(j, AL){
if (i > 0 && j != s[i] - 'a')
A[i][j] = A[p[i - 1]][j];
else
A[i][j] = i + (j == s[i] - 'a');
}
int q;
cin >> q;
vector<vector<int>> ans(q);
forn(z, q){
string t;
cin >> t;
int m = t.size();
s += t;
for (int i = n; i < n + m; ++i){
A.push_back(vector<int>(AL));
forn(j, AL){
if (j != s[i] - 'a')
A[i][j] = A[p[i - 1]][j];
else
A[i][j] = i + (j == s[i] - 'a');
}
p.push_back(A[p[i - 1]][s[i] - 'a']);
ans[z].push_back(p[i]);
}
forn(_, m){
p.pop_back();
s.pop_back();
A.pop_back();
}
}
for (auto &it : ans){
for (int x : it)
cout << x << ' ';
cout << '\n';
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 400043;
const int INF = int(1e9);
struct edge
{
int y, c, f;
edge() {};
edge(int y, int c, int f) : y(y), c(c), f(f) {};
};
vector<edge> e;
vector<int> g[N];
int S, T, V;
int d[N], lst[N];
int n1, n2, m, q;
map<pair<int, int>, int> es;
void add_edge(int x, int y, int c)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, 0));
g[y].push_back(e.size());
e.push_back(edge(x, 0, 0));
}
int rem(int x)
{
return e[x].c - e[x].f;
}
bool bfs()
{
for (int i = 0; i < V; i++)
d[i] = INF;
d[S] = 0;
queue<int> q;
q.push(S);
while (!q.empty())
{
int k = q.front();
q.pop();
for (auto y : g[k])
{
if (rem(y) == 0)
continue;
int to = e[y].y;
if (d[to] > d[k] + 1)
{
q.push(to);
d[to] = d[k] + 1;
}
}
}
return d[T] < INF;
}
int dfs(int x, int mx)
{
if (x == T || mx == 0)
return mx;
int sum = 0;
for (; lst[x] < g[x].size(); lst[x]++)
{
int num = g[x][lst[x]];
int r = rem(num);
if (r == 0)
continue;
int to = e[num].y;
if (d[to] != d[x] + 1)
continue;
int pushed = dfs(to, min(r, mx));
if (pushed > 0)
{
e[num].f += pushed;
e[num ^ 1].f -= pushed;
sum += pushed;
mx -= pushed;
if (mx == 0)
return sum;
}
}
return sum;
}
int Dinic()
{
int ans = 0;
while (bfs())
{
for (int i = 0; i < V; i++)
lst[i] = 0;
int f = 0;
do
{
f = dfs(S, INF);
ans += f;
} while (f > 0);
}
return ans;
}
int main()
{
scanf("%d %d %d %d", &n1, &n2, &m, &q);
S = n1 + n2;
T = S + 1;
V = T + 1;
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
es[make_pair(x, y)] = i + 1;
add_edge(x, n1 + y, 1);
}
for (int i = 0; i < n1; i++)
add_edge(S, i, 1);
for (int i = 0; i < n2; i++)
add_edge(i + n1, T, 1);
Dinic();
bfs();
vector<int> vertex_cover;
map<int, int> index;
set<int> matched;
long long sum = 0;
for (int i = 0; i < n1; i++)
if (d[i] == INF)
{
vertex_cover.push_back(i + 1);
for (auto ei : g[i])
if (e[ei].f == 1)
{
int idx = es[make_pair(i, e[ei].y - n1)];
index[i + 1] = idx;
sum += idx;
matched.insert(idx);
}
}
for (int i = 0; i < n2; i++)
if (d[i + n1] != INF)
{
vertex_cover.push_back(-(i + 1));
for (auto ei : g[i + n1])
if (e[ei].f == -1)
{
int idx = es[make_pair(e[ei].y, i)];
index[-(i + 1)] = idx;
sum += idx;
matched.insert(idx);
}
}
for (int i = 0; i < q; i++)
{
int s;
scanf("%d", &s);
if (s == 1)
{
puts("1");
int v = vertex_cover.back();
vertex_cover.pop_back();
printf("%d\n", v);
sum -= index[v];
matched.erase(index[v]);
printf("%lld\n", sum);
}
else
{
printf("%d\n", (int)matched.size());
for(auto x : matched) printf("%d ", x);
puts("");
}
fflush(stdout);
}
}