Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
input()
xs = []
ys = []
for j in range(3):
x, y = map(int, input().split())
xs.append(x)
ys.append(y)
print('YES' if len(set(xs)) == 3 or len(set(ys)) == 3 else 'NO')
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
x = a[0]
a = sorted(a[1:])
for y in a:
if y > x:
x += (y - x + 1) // 2
print(x)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
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;
}
const int N = 143;
int n;
int a[N][N];
int dp[N][N];
bool check(int cnt, int last)
{
for(int i = 0; i < cnt; i++)
{
if(a[i][cnt - 1] == 0) continue;
if(a[i][cnt - 1] == 1 && last > i) return false;
if(a[i][cnt - 1] == 2 && last <= i) return false;
}
return true;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
cin >> a[i][j];
}
if(a[0][0] != 2) dp[1][0] = 2;
for(int i = 1; i < n; i++)
for(int j = 0; j < i; j++)
for(int k : vector<int>({j, i}))
if(check(i + 1, k))
dp[i + 1][k] = add(dp[i + 1][k], dp[i][j]);
int ans = 0;
for(int i = 0; i < n; i++)
ans = add(ans, dp[n][i]);
cout << ans << endl;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
int k = count(s.begin(), s.end(), '1');
for (int x = 1 << k; x <= (1 << n) - (1 << (n - k)) + 1; ++x)
cout << x << ' ';
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> c(n);
forn(i, n){
scanf("%d", &c[i]);
--c[i];
}
vector<int> x(m);
forn(i, m) scanf("%d", &x[i]);
vector<long long> g(m);
forn(i, n - 1){
g[c[i]] |= 1ll << c[i + 1];
g[c[i + 1]] |= 1ll << c[i];
}
g[c[0]] |= 1ll << c[0];
g[c[n - 1]] |= 1ll << c[n - 1];
int mid = m / 2;
vector<int> dp(1 << mid, 1e9);
forn(mask, 1 << (m - mid)){
long long chk = 0;
int tot = 0;
forn(i, m - mid){
if ((mask >> i) & 1)
tot += x[i + mid];
else
chk |= g[i + mid];
}
if (((chk >> mid) | mask) != mask)
continue;
chk &= (1ll << mid) - 1;
dp[chk] = min(dp[chk], tot);
}
forn(i, mid) forn(mask, 1 << mid) if (!((mask >> i) & 1)){
dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask]);
}
int ans = 1e9;
forn(mask, 1 << mid){
long long chk = 0;
int tot = 0;
forn(i, mid){
if ((mask >> i) & 1)
tot += x[i];
else
chk |= g[i];
}
chk &= (1ll << mid) - 1;
if ((chk | mask) != mask)
continue;
ans = min(ans, dp[mask] + tot);
}
printf("%d\n", ans);
return 0;
}
Idea: shnirelman
Tutorial
Tutorial is loading...
Solution (shnirelman)
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using li = long long;
using ld = long double;
using pii = pair<int, int>;
const int INF = 2e9 + 13;
const li INF64 = 2e18 + 13;
const int M = 998244353;
const int A = 2e5 + 13;
const int N = 2e5 + 13;
const int B = 2000;
const int SQRTA = 500;
const int K = N / B + 113;
int val[N];
vector<int> g[N];
int sz[N];
int gr[N];
int leaf[N], group_root[N];
int par[N];
bool heavy[N];
int tin[N], tout[N], T = 0, mid[N];
int et[N];
int valet[N];
void dfs1(int v, int pr, int depth) {
par[v] = pr;
sz[v] = 1;
int mx = -1;
for(int i = 0; i < g[v].size(); i++) {
int u = g[v][i];
if(u != pr) {
dfs1(u, v, depth + 1);
sz[v] += sz[u];
if(mx == -1 || sz[g[v][mx]] < sz[u])
mx = i;
}
}
if(mx != -1)
swap(g[v][mx], g[v][0]);
}
void dfs2(int v) {
et[T] = v;
tin[v] = T++;
for(int u : g[v]) {
if(u != par[v])
dfs2(u);
}
tout[v] = T;
}
struct Query {
int ind;
int v, u;
int lv, rv, lu, ru;
int b;
Query() {};
};
bool cmp(const Query& a, const Query& b) {
if(a.b != b.b)
return a.b < b.b;
else
return a.lu < b.lu;
}
int cnt[A];
int block_index[A];
int block_mx[A];
int block_cnt_of_cnt[A / SQRTA + 13][A];
inline void insert(int i) {
block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
cnt[valet[i]]++;
block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
if(cnt[valet[i]] > block_mx[block_index[valet[i]]])
block_mx[block_index[valet[i]]]++;
}
inline void erase(int i) {
if(cnt[valet[i]] == block_mx[block_index[valet[i]]] && block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]] == 1)
block_mx[block_index[valet[i]]]--;
block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
cnt[valet[i]]--;
block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
}
int get_mode() {
int mx = 0;
for(int i = 0; i < A / SQRTA + 1; i++)
mx = max(mx, block_mx[i]);
for(int i = 0; ; i++) {
if(block_mx[i] == mx) {
for(int j = i * SQRTA; ; j++) {
if(cnt[j] == mx)
return j;
}
}
}
}
Query queries[N];
int ans[N];
void solve() {
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> val[i];
for(int i = 1; i < n; i++) {
int v, u;
cin >> v >> u;
v--;
u--;
g[v].push_back(u);
g[u].push_back(v);
}
dfs1(0, -1, 0);
vector<pii> ord(n);
for(int i = 0; i < n; i++) {
ord[i] = {sz[i], i};
gr[i] = -1;
}
sort(ord.begin(), ord.end());
for(int i = 0; i < n; i++) {
if(sz[i] >= B)
heavy[i] = true;
}
int cur = 0;
for(int i = 0; i < n; i++) {
int v = ord[i].s;
if(sz[v] < B || gr[v] != -1)
continue;
leaf[cur] = v;
int u = v;
while(gr[u] == -1 && sz[u] - sz[v] < B) {
gr[u] = cur;
group_root[cur] = u;
u = par[u];
}
cur++;
}
dfs2(0);
for(int i = 0; i < n; i++) {
if(sz[i] < B) {
gr[i] = cur + tin[i] / B;
}
}
for(int i = 0; i < n; i++)
valet[i] = val[et[i]];
for(int i = 0; i < A; i++) {
block_index[i] = i / SQRTA;
}
int q;
cin >> q;
for(int i = 0; i < q; i++) {
queries[i].ind = i;
cin >> queries[i].v >> queries[i].u;
queries[i].v--;
queries[i].u--;
queries[i].lv = tin[queries[i].v];
queries[i].rv = tout[queries[i].v];
queries[i].lu = tin[queries[i].u];
queries[i].ru = tout[queries[i].u];
if(queries[i].lv > queries[i].lu) {
swap(queries[i].v, queries[i].u);
swap(queries[i].lv, queries[i].lu);
swap(queries[i].rv, queries[i].ru);
}
queries[i].b = gr[queries[i].v];
}
sort(queries, queries + q, cmp);
int lv = 0, rv = 0, lu = 0, ru = 0;
li fir = 0, sec = 0;
int hs = 0;
for(int i = 0; i < q; i++) {
int qlv = queries[i].lv;
int qrv = queries[i].rv;
int qlu = queries[i].lu;
int qru = queries[i].ru;
fir += abs(lv - qlv) + abs(rv - qrv);
sec += abs(lu - qlu) + abs(ru - qru);
if(queries[i].b < cur) {
while(rv < qrv)
insert(rv++);
while(lv > qlv)
insert(--lv);
while(rv > qrv)
erase(--rv);
while(lv < qlv)
erase(lv++);
} else {
while(rv > lv)
erase(--rv);
lv = qlv;
rv = lv;
while(rv < qrv)
insert(rv++);
}
while(ru < qru)
insert(ru++);
while(lu > qlu)
insert(--lu);
while(ru > qru)
erase(--ru);
while(lu < qlu)
erase(lu++);
ans[queries[i].ind] = get_mode();
}
for(int i = 0; i < q; i++)
cout << ans[i] << endl;
}
mt19937 rnd(1);
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt", "r", stdin);
solve();
}