Идея: vovuh
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
long long n, k;
cin >> n >> k;
long long cf = (n + k - 1) / k;
k *= cf;
cout << (k + n - 1) / n << endl;
}
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
const int INF = int(1e9);
int main() {
int t; cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
vector<int> p(n);
for (int i = 0; i < n; i++)
cin >> p[i];
li x = 0;
li pSum = p[0];
for (int i = 1; i < n; i++) {
x = max(x, (100ll * p[i] - k * pSum + k - 1) / k);
pSum += p[i];
}
cout << x << endl;
}
return 0;
}
1476C - Наидлиннейший простой цикл
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> c(n), a(n), b(n);
for (int i = 0; i < n; i++)
cin >> c[i];
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
li ans = 0;
li lstLen = 0;
for (int i = 1; i < n; i++) {
li curLen = c[i] + 1ll + abs(a[i] - b[i]);
if (a[i] != b[i])
curLen = max(curLen, c[i] + 1ll + lstLen - abs(a[i] - b[i]));
ans = max(ans, curLen);
lstLen = curLen;
}
cout << ans << endl;
}
return 0;
};
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int INF = int(1e9);
char buf[300043];
int main()
{
int t;
scanf("%d", &t);
for(int _ = 0; _ < t; _++)
{
int n;
scanf("%d", &n);
scanf("%s", buf);
string s = buf;
vector<vector<int>> g(2 * n + 2);
for(int i = 0; i < n; i++)
if(s[i] == 'L')
{
g[(i + 1) * 2].push_back(i * 2 + 1);
g[i * 2 + 1].push_back((i + 1) * 2);
}
else
{
g[i * 2].push_back((i + 1) * 2 + 1);
g[(i + 1) * 2 + 1].push_back(i * 2);
}
vector<int> comp(2 * n + 2, -1);
vector<int> cnt;
for(int i = 0; i < 2 * n + 2; i++)
{
if(comp[i] != -1) continue;
int c = 1;
int cc = cnt.size();
queue<int> q;
comp[i] = cc;
q.push(i);
while(!q.empty())
{
int k = q.front();
q.pop();
for(auto y : g[k])
{
if(comp[y] == -1)
{
c++;
comp[y] = cc;
q.push(y);
}
}
}
cnt.push_back(c);
}
for(int i = 0; i <= n; i++)
printf("%d%c", cnt[comp[i * 2]], " \n"[i == n]);
}
}
Решение 2 (BledDest)
t = int(input())
for _ in range(t):
n = int(input())
s = input()
dpl = [i for i in range(n + 1)]
dpr = [i for i in range(n + 1)]
for i in range(n + 1):
if i == 0 or s[i - 1] == 'R':
dpl[i] = i
elif i == 1 or s[i - 2] == 'L':
dpl[i] = i - 1
else:
dpl[i] = dpl[i - 2]
for i in range(n, -1, -1):
if i == n or s[i] == 'L':
dpr[i] = i
elif i == n - 1 or s[i + 1] == 'R':
dpr[i] = i + 1
else:
dpr[i] = dpr[i + 2]
ans = [(dpr[i] - dpl[i]) + 1 for i in range(n + 1)]
print(*ans)
1476E - Сопоставление шаблонов
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
struct pattern{
string s;
int i;
};
bool operator <(const pattern &a, const pattern &b){
return a.s < b.s;
}
vector<vector<int>> g;
vector<int> used, ord;
bool cyc;
void ts(int v){
used[v] = 1;
for (int u : g[v]){
if (used[u] == 0)
ts(u);
else if (used[u] == 1)
cyc = true;
if (cyc)
return;
}
used[v] = 2;
ord.push_back(v);
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, m, k;
cin >> n >> m >> k;
vector<pattern> p(n);
g.assign(n, vector<int>());
forn(i, n){
cin >> p[i].s;
p[i].i = i;
}
sort(p.begin(), p.end());
pattern nw;
nw.s = string(k, '_');
forn(i, m){
string cur;
int mt;
cin >> cur >> mt;
--mt;
bool ok = false;
forn(mask, 1 << k){
forn(j, k)
nw.s[j] = ((mask >> j) & 1 ? cur[j] : '_');
auto it = lower_bound(p.begin(), p.end(), nw);
if (it != p.end() && it->s == nw.s){
if (it->i != mt)
g[mt].push_back(it->i);
else
ok = true;
}
}
if (!ok){
puts("NO");
return 0;
}
}
used.assign(n, 0);
cyc = false;
ord.clear();
forn(i, n) if (!used[i]){
ts(i);
if (cyc){
cout << "NO\n";
return 0;
}
}
reverse(ord.begin(), ord.end());
cout << "YES\n";
forn(i, n)
cout << ord[i] + 1 << " ";
cout << "\n";
return 0;
}
Решение 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
struct pattern{
string s;
int i;
};
bool operator <(const pattern &a, const pattern &b){
return a.s < b.s;
}
vector<vector<int>> g;
vector<int> used, ord;
bool cyc;
void ts(int v){
used[v] = 1;
for (int u : g[v]){
if (used[u] == 0)
ts(u);
else if (used[u] == 1)
cyc = true;
if (cyc)
return;
}
used[v] = 2;
ord.push_back(v);
}
struct node{
int nxt[28];
int term;
node(){
memset(nxt, -1, sizeof(nxt));
term = -1;
}
};
vector<node> trie;
void add(const string &s, int i){
int cur = 0;
for (char c : s){
int x = c - '_';
if (trie[cur].nxt[x] == -1){
trie[cur].nxt[x] = trie.size();
trie.push_back(node());
}
cur = trie[cur].nxt[x];
}
trie[cur].term = i;
}
bool check(int i, int v, const string &s, int mt){
if (i == int(s.size())){
assert(trie[v].term != -1);
if (trie[v].term != mt)
g[mt].push_back(trie[v].term);
else
return true;
return false;
}
bool res = false;
if (trie[v].nxt[s[i] - '_'] != -1 && check(i + 1, trie[v].nxt[s[i] - '_'], s, mt))
res = true;
if (trie[v].nxt[0] != -1 && check(i + 1, trie[v].nxt[0], s, mt))
res = true;
return res;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
trie = vector<node>(1);
int n, m, k;
cin >> n >> m >> k;
g.assign(n, vector<int>());
forn(i, n){
string cur;
cin >> cur;
add(cur, i);
}
pattern nw;
nw.s = string(k, '_');
forn(i, m){
string cur;
int mt;
cin >> cur >> mt;
if (!check(0, 0, cur, mt - 1)){
cout << "NO\n";
return 0;
}
}
used.assign(n, 0);
cyc = false;
ord.clear();
forn(i, n) if (!used[i]){
ts(i);
if (cyc){
cout << "NO\n";
return 0;
}
}
reverse(ord.begin(), ord.end());
cout << "YES\n";
forn(i, n)
cout << ord[i] + 1 << " ";
cout << "\n";
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int INF = int(1e9);
struct segTree
{
int n;
bool mx;
vector<int> t;
void fix(int v)
{
t[v] = (mx ? max(t[v * 2 + 1], t[v * 2 + 2]) : min(t[v * 2 + 1], t[v * 2 + 2]));
}
void build(int v, int l, int r)
{
if(l == r - 1)
t[v] = (mx ? -INF : INF);
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
fix(v);
}
}
void upd(int v, int l, int r, int pos, int val)
{
if(l == r - 1)
t[v] = (mx ? max(t[v], val) : min(t[v], val));
else
{
int m = (l + r) / 2;
if(pos < m)
upd(v * 2 + 1, l, m, pos, val);
else
upd(v * 2 + 2, m, r, pos, val);
fix(v);
}
}
int get(int v, int l, int r, int L, int R)
{
if(L >= R)
return (mx ? -INF : INF);
if(l == L && r == R)
return t[v];
int m = (l + r) / 2;
int lf = get(v * 2 + 1, l, m, L, min(R, m));
int rg = get(v * 2 + 2, m, r, max(m, L), R);
return (mx ? max(lf, rg) : min(lf, rg));
}
void upd(int pos, int val)
{
upd(0, 0, n, pos, val);
}
int get(int L, int R)
{
return get(0, 0, n, L, R);
}
void build()
{
return build(0, 0, n);
}
segTree() {};
segTree(int n, bool mx) : n(n), mx(mx)
{
t.resize(4 * n);
}
};
int main()
{
int t;
scanf("%d", &t);
for(int _ = 0; _ < t; _++)
{
int n;
scanf("%d", &n);
vector<int> p(n);
for(int i = 0; i < n; i++)
scanf("%d", &p[i]);
vector<int> dp(n + 1, -INF);
vector<int> par(n + 1, -2);
dp[0] = 0;
par[0] = -1;
vector<int> lf(n), rg(n);
for(int i = 0; i < n; i++)
{
lf[i] = max(1, i - p[i] + 1);
rg[i] = min(n, i + p[i] + 1);
}
segTree sn(n + 1, false);
segTree sx(n, true);
sn.build();
sx.build();
for(int i = 0; i < n; i++)
sx.upd(i, rg[i]);
sn.upd(0, 0);
for(int i = 1; i <= n; i++)
{
int j = i - 1;
int k = lf[j] - 1;
int m = sn.get(k, n + 1);
if(m != INF)
{
int nval = max(sx.get(m, i - 1), i - 1);
if(nval > dp[i])
{
dp[i] = nval;
par[i] = m;
}
}
if(dp[j] >= i && max(dp[j], rg[j]) > dp[i])
{
dp[i] = max(dp[j], rg[j]);
par[i] = -1;
}
if(dp[j] > dp[i])
{
dp[i] = dp[j];
par[i] = -1;
}
sn.upd(dp[i], i);
}
if(dp[n] != n)
puts("NO");
else
{
puts("YES");
string ans;
int cur = n;
while(cur != 0)
{
if(par[cur] == -1)
{
cur--;
ans += "R";
}
else
{
int pcur = par[cur];
int diff = cur - pcur;
ans += "L";
for(int j = 0; j < diff - 1; j++)
ans += "R";
cur = pcur;
}
}
reverse(ans.begin(), ans.end());
puts(ans.c_str());
}
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef pair<int, int> pt;
const int N = 100 * 1000 + 13;
const int P = 2000;
struct query {
int t, l, r, k, i;
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<query> q;
vector<array<int, 3>> upd;
forn(i, m) {
int tp;
scanf("%d", &tp);
if (tp == 1) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
q.push_back({sz(upd), l - 1, r - 1, k, sz(q)});
} else {
int p, x;
scanf("%d%d", &p, &x); --p;
upd.push_back({p, a[p], x});
a[p] = x;
}
}
sort(q.begin(), q.end(), [](const query &a, const query &b) {
if (a.t / P != b.t / P)
return a.t < b.t;
if (a.l / P != b.l / P)
return a.l < b.l;
if ((a.l / P) & 1)
return a.r < b.r;
return a.r > b.r;
});
for (int i = sz(upd) - 1; i >= 0; --i)
a[upd[i][0]] = upd[i][1];
vector<int> cnt(N), ord(N);
vector<pt> bounds(N, {N, 0});
bounds[0] = {0, N - 1};
int L = 0, R = -1, T = 0;
auto add = [&](int x) {
int c = cnt[x];
++ord[bounds[c].x];
bounds[c + 1].y = bounds[c].x;
if (bounds[c + 1].x == N)
bounds[c + 1].x = bounds[c].x;
if (bounds[c].x == bounds[c].y)
bounds[c].x = N - 1;
++bounds[c].x;
++cnt[x];
};
auto rem = [&](int x) {
int c = cnt[x];
--ord[bounds[c].y];
if (bounds[c - 1].x == N)
bounds[c - 1].y = bounds[c].y;
bounds[c - 1].x = bounds[c].y;
if (bounds[c].x == bounds[c].y)
bounds[c].x = N;
--bounds[c].y;
--cnt[x];
};
auto apply = [&](int i, int fl) {
int p = upd[i][0];
int x = upd[i][fl + 1];
if (L <= p && p <= R) {
rem(a[p]);
add(x);
}
a[p] = x;
};
vector<int> ans(sz(q));
for (auto qr : q) {
int t = qr.t, l = qr.l, r = qr.r, k = qr.k;
while (T < t) apply(T++, 1);
while (T > t) apply(--T, 0);
while (R < r) add(a[++R]);
while (L > l) add(a[--L]);
while (R > r) rem(a[R--]);
while (L < l) rem(a[L++]);
int res = N;
for (int i = 0, j = 0, sum = 0; i < N && ord[i] > 0; i = bounds[ord[i]].y + 1) {
while (j < N && ord[j] > 0 && sum < k) {
sum += bounds[ord[j]].y - bounds[ord[j]].x + 1;
j = bounds[ord[j]].y + 1;
}
if (sum >= k) res = min(res, ord[i] - ord[j - 1]);
sum -= bounds[ord[i]].y - bounds[ord[i]].x + 1;
}
if (res == N) res = -1;
ans[qr.i] = res;
}
for (int x : ans) printf("%d\n", x);
}