Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
for t in range(int(input())):
n = input()
l = filter(lambda x : x <= 2048, map(int, input().split()) )
print('YES' if sum(l) >= 2048 else 'NO')
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (PikMike)
n = int(input())
for i in range(n):
print(''.join(['W' if (i + j) % 2 == 0 else 'B' for j in range(n)]))
Idea: Roms
Tutorial
Tutorial is loading...
Solution 1 (BledDest)
t = int(input())
for i in range(t):
c, m, x = map(int, input().split())
d = max(c, m) - min(c, m)
x += d
if(c > m):
c -= d
else:
m -= d
ans = min(c, m, x)
c -= ans
m -= ans
x -= ans
ans += (c + m) // 3
print(ans)
Solution 2 (PikMike)
#include <bits/stdc++.h>
using namespace std;
int main(){
int q;
cin >> q;
for (int i = 0; i < q; ++i){
int c, m, x;
cin >> c >> m >> x;
int l = 0, r = min(c, m);
int ans = 0;
while (l <= r){
int mid = (l + r) / 2;
if (c + m + x - 2 * mid >= mid){
l = mid + 1;
ans = mid;
}
else{
r = mid - 1;
}
}
cout << ans << "\n";
}
}
1221D - Make The Fence Great Again
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
const long long INF64 = (long long)(1e18) + 100;
int t;
int n;
int a[N];
int b[N];
long long dp[3][N];
long long calc(int add, int pos){
long long &res = dp[add][pos];
if(res != -1) return res;
res = INF64;
if(pos == n) return res = 0;
for(long long x = 0; x <= 2; ++x)
if(pos == 0 || a[pos] + x != a[pos - 1] + add)
res = min(res, calc(x, pos + 1) + x * b[pos]);
return res;
}
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
scanf("%d", b + i);
}
for(int i = 0; i <= n; ++i)
dp[0][i] = dp[1][i] = dp[2][i] = -1;
printf("%lld\n", calc(0, 0));
}
return 0;
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 99;
int t;
int a, b;
string s;
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> a >> b >> s;
vector <int> v;
int l = 0;
while(l < s.size()){
if(s[l] == 'X'){
++l;
continue;
}
int r = l + 1;
while(r < s.size() && s[r] == '.') ++r;
v.push_back(r - l);
l = r;
}
bool ok = true;
int id = -1;
int cnt = 0;
for(int i = 0; i < v.size(); ++i){
if(b <= v[i] && v[i] < a) ok = false;
if(b + b <= v[i]){
if(id == -1) id = i;
else ok = false;
}
if(a <= v[i] && v[i] < b + b) ++cnt;
}
if(!ok){
cout << "NO" << endl;
continue;
}
if(id == -1){
if(cnt & 1) cout << "YES" << endl;
else cout << "NO" << endl;
continue;
}
ok = false;
int sz = v[id];
assert(sz >= a);
for(int rem1 = 0; sz - a - rem1 >= 0; ++rem1){
int rem2 = sz - a - rem1;
int ncnt = cnt;
if((rem1 >= b + b) || (b <= rem1 && rem1 < a)) continue;
if((rem2 >= b + b) || (b <= rem2 && rem2 < a)) continue;
if(rem1 >= a) ++ncnt;
if(rem2 >= a) ++ncnt;
if(ncnt % 2 == 0) ok = true;
}
if(ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long li;
typedef pair<int, int> pt;
const int N = 1000 * 1000 + 13;
int n;
pair<pt, int> a[N];
vector<int> vals;
vector<pt> ev[N];
pair<li, int> t[4 * N];
li add[4 * N];
void build(int v, int l, int r) {
if (l == r) {
t[v] = mp(-vals[l], l);
add[v] = 0;
return;
}
int m = (l + r) >> 1;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m + 1, r);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}
void push(int v, int l, int r) {
if (add[v] == 0) return;
t[v].x += add[v];
if (l != r) {
add[v * 2 + 1] += add[v];
add[v * 2 + 2] += add[v];
}
add[v] = 0;
}
void upd(int v, int l, int r, int L, int R, int val) {
push(v, l, r);
if (L > R) return;
if (l == L && r == R) {
add[v] += val;
push(v, l, r);
return;
}
int m = (l + r) >> 1;
upd(v * 2 + 1, l, m, L, min(m, R), val);
upd(v * 2 + 2, m + 1, r, max(m + 1, L), R, val);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}
pair<li, int> get(int v, int l, int r, int L, int R) {
push(v, l, r);
if (L > R) return mp(-li(1e18), 0);
if (l == L && r == R) return t[v];
int m = (l + r) >> 1;
auto r1 = get(v * 2 + 1, l, m, L, min(m, R));
auto r2 = get(v * 2 + 2, m + 1, r, max(m + 1, L), R);
return max(r1, r2);
}
int main() {
scanf("%d", &n);
forn(i, n) scanf("%d%d%d", &a[i].x.x, &a[i].x.y, &a[i].y);
forn(i, n) {
vals.pb(a[i].x.x);
vals.pb(a[i].x.y);
}
vals.pb(0);
sort(all(vals));
vals.pb(vals.back() + 1);
vals.resize(unique(all(vals)) - vals.begin());
forn(i, n) {
int x = lower_bound(all(vals), a[i].x.x) - vals.begin();
int y = lower_bound(all(vals), a[i].x.y) - vals.begin();
ev[min(x, y)].pb(mp(max(x, y), a[i].y));
}
n = sz(vals);
build(0, 0, n - 1);
li ans = -1;
int ansl = -1, ansr = -1;
for (int i = sz(vals) - 1; i >= 0; i--) {
for (auto it : ev[i]) upd(0, 0, n - 1, it.x, n - 1, it.y);
auto cur = get(0, 0, n - 1, i, n - 1);
if (cur.x + vals[i] > ans) {
ans = cur.x + vals[i];
ansl = vals[i]; ansr = vals[cur.y];
}
}
printf("%lld\n%d %d %d %d\n", ans, ansl, ansl, ansr, ansr);
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 40;
const int M = 20;
long long incident_mask[N];
vector<int> g[N];
int n, m;
long long ans = 0;
long long cntmask[1 << M];
long long binpow(long long x, long long y)
{
long long z = 1;
while(y > 0)
{
if(y % 2 == 1) z *= x;
x *= x;
y /= 2;
}
return z;
}
int used[N];
void dfs(int x, int c)
{
if(used[x])
return;
used[x] = c;
for(auto y : g[x])
dfs(y, 3 - c);
}
long long countIsolated()
{
long long ans = 0;
for(int i = 0; i < n; i++)
if(g[i].empty())
ans++;
return ans;
}
long long countComponents()
{
memset(used, 0, sizeof used);
long long ans = 0;
for(int i = 0; i < n; i++)
if(!used[i])
{
ans++;
dfs(i, 1);
}
return ans;
}
bool bipartite()
{
memset(used, 0, sizeof used);
for(int i = 0; i < n; i++)
if(!used[i])
dfs(i, 1);
for(int i = 0; i < n; i++)
for(auto j : g[i])
if(used[i] == used[j])
return false;
return true;
}
long long countIndependentSets()
{
int m1 = min(n, 20);
int m2 = n - m1;
//cerr << m1 << " " << m2 << endl;
memset(cntmask, 0, sizeof cntmask);
for(int i = 0; i < (1 << m1); i++)
{
long long curmask = 0;
bool good = true;
for(int j = 0; j < m1; j++)
{
if((i & (1 << j)) == 0)
continue;
if(curmask & (1 << j))
good = false;
curmask |= ((1 << j) | incident_mask[j]);
}
if(good)
{
cntmask[curmask >> m1]++;
}
}
for(int i = 0; i < m2; i++)
for(int j = 0; j < (1 << m2); j++)
if(j & (1 << i))
cntmask[j] += cntmask[j ^ (1 << i)];
long long ans = 0;
for(int i = 0; i < (1 << m2); i++)
{
long long curmask = 0;
bool good = true;
for(int j = m1; j < n; j++)
{
if((i & (1 << (j - m1))) == 0)
continue;
if(curmask & (1ll << j))
good = false;
curmask |= (1ll << j) | incident_mask[j];
}
if(good)
{
//cerr << i << endl;
ans += cntmask[(i ^ ((1 << m2) - 1))];
}
}
return ans;
}
long long calc(int mask)
{
if(mask == 0)
return binpow(2, n);
if(mask == 1 || mask == 4)
return countIndependentSets();
if(mask == 2)
return binpow(2, countComponents());
if(mask == 3 || mask == 6)
return binpow(2, countIsolated());
if(mask == 5)
return (bipartite() ? binpow(2, countComponents()) : 0);
if(mask == 7)
return (m == 0 ? binpow(2, n) : 0);
return 0;
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
incident_mask[x] ^= (1ll << y);
incident_mask[y] ^= (1ll << x);
}
for(int i = 0; i < 8; i++)
{
//cerr << i << " " << calc(i) << endl;
if(__builtin_popcount(i) % 2 == 0)
ans += calc(i);
else
ans -= calc(i);
}
cout << ans << endl;
return 0;
}