Идея: adedalic
Разбор
Tutorial is loading...
Решение (Ne0n25)
for i in range(int(input())):
a, b, c = map(int, input().split())
if (a + b + c) % 9 != 0:
print("NO")
else:
print("YES" if min(a, b, c) >= (a + b + c) // 9 else "NO")
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Ne0n25)
for t in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
cur = [0, 0]
for i in range(n):
cur[i % 2] += a[i] - 1
for j in range(2):
if 2 * cur[j] > s:
continue
for i in range(n):
if i % 2 == j:
a[i] = 1
break
print(*a)
Идея: KAN
Разбор
Tutorial is loading...
Решение (pikmike)
def inside(l, r, x):
return min(l, r) <= x <= max(l, r)
def sg(x):
return -1 if x < 0 else int(x > 0)
for _ in range(int(input())):
n = int(input())
qs = []
for i in range(n):
qs.append(list(map(int, input().split())))
qs.append([4*10**9, 0])
ans = 0
pos, dr, lft = 0, 0, 0
for i in range(n):
t, x = qs[i]
tn = qs[i + 1][0]
if lft == 0:
lft = abs(pos - x)
dr = sg(x - pos)
tmp = min(lft, tn - t)
if inside(pos, pos + dr * tmp, x):
ans += 1
pos += dr * tmp
lft -= tmp
print(ans)
Идея: adedalic
Разбор
Tutorial is loading...
Решение 1 (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
const int INF = int(1e9);
int n;
vector<int> b;
inline bool read() {
if(!(cin >> n))
return false;
b.resize(n);
fore (i, 0, n)
cin >> b[i];
return true;
}
bool ok(const vector<int> &a, const vector<int> &b, int cnt) {
fore (i, 0, cnt) {
if (a[i] >= b[sz(b) - cnt + i])
return false;
}
return true;
}
inline void solve() {
vector<int> nb;
fore (i, 1, 2 * n + 1) {
if (!binary_search(b.begin(), b.end(), i))
nb.push_back(i);
}
int mx[2] = {-1, -1};
fore (k, 0, 2) {
int lf = 0, rg = n + 1;
while (rg - lf > 1) {
int mid = (lf + rg) / 2;
if (ok(b, nb, mid))
lf = mid;
else
rg = mid;
}
mx[k] = lf;
if (!ok(nb, b, n - lf)) {
cout << 0 << endl;
return;
}
swap(b, nb);
}
assert(n - mx[1] <= mx[0]);
cout << mx[0] - (n - mx[1]) + 1 << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t; cin >> t;
while(t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Решение 2 (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
const int INF = int(1e9);
int n;
vector<int> b;
inline bool read() {
if(!(cin >> n))
return false;
b.resize(n);
fore (i, 0, n)
cin >> b[i];
return true;
}
int getMax(const vector<int> &a, const vector<int> &b) {
int uk = 0;
fore (i, 0, sz(a)) {
while (uk < sz(b) && b[uk] < a[i])
uk++;
if (uk >= sz(b))
return i;
uk++;
}
return sz(a);
}
inline void solve() {
vector<int> nb;
fore (i, 1, 2 * n + 1) {
if (!binary_search(b.begin(), b.end(), i))
nb.push_back(i);
}
int mxX = getMax(b, nb);
int mnX = n - getMax(nb, b);
cout << mxX - mnX + 1 << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t; cin >> t;
while(t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (pikmike)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
vector<vector<int>> g, h, ng;
vector<int> rk, p;
int getp(int a){
return a == p[a] ? a : p[a] = getp(p[a]);
}
void unite(int a, int b){
a = getp(a), b = getp(b);
if (a == b) return;
if (rk[a] < rk[b]) swap(a, b);
rk[a] += rk[b];
p[b] = a;
}
vector<vector<int>> comp;
vector<int> ord;
vector<int> used;
bool fl;
void ts(int v, const vector<vector<int>> &g){
used[v] = 1;
for (int u : g[v]){
if (used[u] == 0)
ts(u, g);
else if (used[u] == 1)
fl = false;
if (!fl) return;
}
ord.push_back(v);
used[v] = 2;
}
bool topsort(const vector<vector<int>> &g){
int n = g.size();
used.assign(n, 0);
ord.clear();
fl = true;
forn(i, n) if (!used[i]){
ts(i, g);
if (!fl) return false;
}
reverse(ord.begin(), ord.end());
return true;
}
vector<int> pos;
bool dfs(int v){
for (int u : g[v]){
if (pos[u] < pos[v])
return false;
if (!dfs(u))
return false;
}
return true;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
g.resize(n);
h.resize(n);
ng.resize(n);
int rt = -1;
forn(i, n){
int p;
scanf("%d", &p);
--p;
if (p == -1)
rt = i;
else
g[p].push_back(i);
}
rk.assign(n, 1);
p.resize(n);
iota(p.begin(), p.end(), 0);
forn(i, m){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
h[v].push_back(u);
unite(v, u);
}
if (!topsort(h)){
puts("0");
return 0;
}
auto ord1 = ord;
vector<int> pos1(n);
forn(i, n) pos1[ord1[i]] = i;
forn(v, n) for (int u : g[v]) if (getp(v) != getp(u))
ng[getp(v)].push_back(getp(u));
if (!topsort(ng)){
puts("0");
return 0;
}
comp.resize(n);
forn(i, n) comp[getp(i)].push_back(i);
vector<int> fin;
for (int it : ord){
sort(comp[it].begin(), comp[it].end(), [&](int v, int u){ return pos1[v] < pos1[u]; });
for (int v : comp[it])
fin.push_back(v);
}
pos.resize(n);
forn(i, n) pos[fin[i]] = i;
if (!dfs(rt)){
puts("0");
return 0;
}
for (int v : fin)
printf("%d ", v + 1);
puts("");
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int N = 22;
int dp[2][1 << N];
int val[2 * N];
int main() {
int n, x, y;
scanf("%d%d%d", &n, &x, &y);
int k = x + y;
int m = max(x, y);
int FULL = (1 << m) - 1;
for (int i = 0; i < k; ++i)
val[i] = n / k + (i < n % k);
for (int mask = 0; mask < (1 << m); ++mask)
dp[0][mask] = -INF;
dp[0][0] = 0;
for (int i = 0; i < k; ++i) {
for (int mask = 0; mask < (1 << m); ++mask)
dp[1][mask] = -INF;
for (int mask = 0; mask < (1 << m); ++mask) {
if (dp[0][mask] == -INF)
continue;
int nmask = (mask << 1) & FULL;
dp[1][nmask] = max(dp[1][nmask], dp[0][mask]);
if (((mask >> (x - 1)) & 1) | ((mask >> (y - 1)) & 1))
continue;
nmask |= 1;
dp[1][nmask] = max(dp[1][nmask], dp[0][mask] + val[i]);
}
swap(dp[0], dp[1]);
}
int ans = 0;
for (int mask = 0; mask < (1 << m); ++mask)
ans = max(ans, dp[0][mask]);
printf("%d\n", ans);
}