Идея: BledDest
Разбор
Tutorial is loading...
Решение (vovuh)
for _ in range(int(input())):
a = [list(map(int, input().split())) for i in range(2)]
cnt = sum([sum(a[i]) for i in range(2)])
if cnt == 0:
print(0)
elif cnt == 4:
print(2)
else:
print(1)
Идея: 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;
cout << 2 << '\n';
for (int i = 1; i <= n; ++i) if (i % 2 != 0)
for (int j = i; j <= n; j *= 2)
cout << j << ' ';
cout << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--){
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(m);
forn(i, m){
scanf("%d", &a[i]);
--a[i];
}
vector<int> cnt(n);
forn(i, m) ++cnt[a[i]];
auto check = [&](int t){
long long fr = 0, need = 0;
forn(i, n){
if (t >= cnt[i])
fr += (t - cnt[i]) / 2;
else
need += cnt[i] - t;
}
return need <= fr;
};
int l = 0, r = 2 * m;
int res = -1;
while (l <= r){
int m = (l + r) / 2;
if (check(m)){
res = m;
r = m - 1;
}
else{
l = m + 1;
}
}
printf("%d\n", res);
}
return 0;
}
1701D - Permutation Restoration
Идея: 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 : b) cin >> x;
vector<pair<int, int>> ev(n);
for (int i = 0; i < n; ++i)
ev[i] = {(i + 1) / (b[i] + 1) + 1, i};
sort(ev.begin(), ev.end());
set<pair<int, int>> s;
int j = 0;
for (int i = 1; i <= n; ++i) {
while (j < n && ev[j].first == i) {
int id = ev[j++].second;
s.insert({b[id] ? (id + 1) / b[id] : n, id});
}
a[s.begin()->second] = i;
s.erase(s.begin());
}
for (int& x : a) cout << x << ' ';
cout << '\n';
}
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение (vovuh)
#include<bits/stdc++.h>
using namespace std;
const int N = 143;
const int K = 5;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int fact[N];
int rfact[N];
int A(int n, int k)
{
return mul(fact[n], rfact[n - k]);
}
int n;
vector<int> g[N];
int x[N];
int y[N];
int dist[N][N];
int color[N];
int dp[N][N];
int cc = 0;
set<int> pts;
vector<int> compsize;
void dfs1(int i)
{
//cerr << i << endl;
if(pts.count(i) == 1) return;
pts.insert(i);
for(auto v : g[i])
{
dfs1(v);
}
}
void dfs2(int i, int c)
{#include <bits/stdc++.h>
using namespace std;
vector<int> zf(const string &s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i <= r) {
z[i] = min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
++z[i];
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int T;
cin >> T;
while (T--) {
int n, m;
string s, t;
cin >> n >> m >> s >> t;
int ans = 1e9;
bool bad = false;
vector<int> lpos(m), rpos(m);
for (int i = 0; i < m; ++i) {
if (i > 0) {
lpos[i] = lpos[i - 1] + 1;
} else {
lpos[i] = 0;
}
while (lpos[i] < n && s[lpos[i]] != t[i]) {
++lpos[i];
}
if (lpos[i] >= n) {
bad = true;
break;
}
}
for (int i = m - 1; i >= 0; --i) {
if (i + 1 < m) {
rpos[i] = rpos[i + 1] - 1;
} else {
rpos[i] = n - 1;
}
while (rpos[i] >= 0 && s[rpos[i]] != t[i]) {
--rpos[i];
}
if (rpos[i] < 0) {
bad = true;
break;
}
}
if (bad) {
cout << -1 << endl;
continue;
}
for (int pos = 0; pos <= n; ++pos) {
string tmp = s.substr(0, pos);
reverse(tmp.begin(), tmp.end());
tmp += "#" + t;
reverse(tmp.begin() + pos + 1, tmp.end());
vector<int> z = zf(tmp);
for (int suf = 0; suf <= m; ++suf) {
if (pos - suf < 0) {
continue;
}
if (suf < m && rpos[suf] < pos) {
continue;
}
if (suf - 1 >= 0 && lpos[suf - 1] > pos) {
continue;
}
int rg = 0;
if (suf != 0) {
int sum = (pos - z[pos + 1 + m - suf]) + (pos - suf);
rg = (sum != 0) + sum;
} else {
rg = pos;
}
ans = min(ans, (n - pos) + rg);
}
}
cout << ans << endl;
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 200043;
const int M = 200001;
typedef array<long long, 3> vec;
typedef array<vec, 3> mat;
vec operator+(const vec& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = a[i] + b[i];
return c;
}
vec operator-(const vec& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = a[i] - b[i];
return c;
}
vec operator*(const mat& a, const vec& b)
{
vec c;
for(int i = 0; i < 3; i++) c[i] = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
c[i] += a[i][j] * b[j];
return c;
}
mat operator*(const mat& a, const mat& b)
{
mat c;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
c[i][j] = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
c[i][k] += a[i][j] * b[j][k];
return c;
}
mat F = {vec({1, 0, 0}), vec({1, 1, 0}), vec({1, 2, 1})};
mat B = {vec({1, 0, 0}), vec({-1, 1, 0}), vec({1, -2, 1})};
mat E = {vec({1, 0, 0}), vec({0, 1, 0}), vec({0, 0, 1})};
vec S = {1, 0, 0};
vec Z = {0, 0, 0};
vec t[4 * N];
mat f[4 * N];
bool active[4 * N];
bool has[N];
int d, q;
vec getVal(int v)
{
if(!active[v]) return Z;
return f[v] * t[v];
}
void recalc(int v)
{
t[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2);
}
void build(int v, int l, int r)
{
if(l == r - 1)
{
f[v] = E;
t[v] = S;
active[v] = false;
}
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
f[v] = E;
recalc(v);
active[v] = true;
}
}
void push(int v)
{
if(f[v] == E) return;
t[v] = f[v] * t[v];
f[v * 2 + 1] = f[v] * f[v * 2 + 1];
f[v * 2 + 2] = f[v] * f[v * 2 + 2];
f[v] = E;
}
void updSegment(int v, int l, int r, int L, int R, bool adv)
{
if(L >= R) return;
if(l == L && r == R)
{
if(adv) f[v] = F * f[v];
else f[v] = B * f[v];
return;
}
push(v);
int m = (l + r) / 2;
updSegment(v * 2 + 1, l, m, L, min(m, R), adv);
updSegment(v * 2 + 2, m, r, max(m, L), R, adv);
recalc(v);
}
void setState(int v, int l, int r, int pos, bool val)
{
if(l == r - 1)
{
active[v] = val;
return;
}
push(v);
int m = (l + r) / 2;
if(pos < m)
setState(v * 2 + 1, l, m, pos, val);
else
setState(v * 2 + 2, m, r, pos, val);
recalc(v);
}
void addPoint(int x)
{
int lf = max(0, x - d);
int rg = x;
if(lf < rg)
updSegment(0, 0, M, lf, rg, true);
setState(0, 0, M, x, true);
}
void delPoint(int x)
{
int lf = max(0, x - d);
int rg = x;
if(lf < rg)
updSegment(0, 0, M, lf, rg, false);
setState(0, 0, M, x, false);
}
void query(int x)
{
if(has[x])
{
has[x] = false;
delPoint(x);
}
else
{
has[x] = true;
addPoint(x);
}
vec res = getVal(0);
printf("%lld\n", (res[2] - res[1]) / 2);
}
int main()
{
scanf("%d %d", &q, &d);
build(0, 0, M);
for(int i = 0; i < q; i++)
{
int x;
scanf("%d", &x);
query(x);
}
}