Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
for t in range(int(input())):
print(input().strip('0').count('0'))
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
val t = readLine()!!.toInt()
for (tc in 1..t) {
val (n, g, b) = readLine()!!.split(' ').map { it.toLong() }
val needG = (n + 1) / 2
var totalG = needG / g * (b + g)
totalG += if (needG % g == 0L) -b else needG % g
println(maxOf(n, totalG))
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
void solve() {
string s;
cin >> s;
vector<bool> used(26);
used[s[0] - 'a'] = true;
string t(1, s[0]);
int pos = 0;
for (int i = 1; i < sz(s); i++) {
if (used[s[i] - 'a']) {
if (pos > 0 && t[pos - 1] == s[i]) {
pos--;
} else if (pos + 1 < sz(t) && t[pos + 1] == s[i]) {
pos++;
} else {
cout << "NO" << endl;
return;
}
} else {
if (pos == 0) {
t = s[i] + t;
} else if (pos == sz(t) - 1) {
t += s[i];
pos++;
} else {
cout << "NO" << endl;
return;
}
}
used[s[i] - 'a'] = true;
}
forn(i, 26) if (!used[i])
t += char(i + 'a');
cout << "YES" << endl << t << endl;
}
int main() {
int tc;
cin >> tc;
forn(i, tc) solve();
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
from math import log2
for t in range(int(input())):
n, m = map(int, input().split())
c = [0] * 61
s = 0
for x in map(int, input().split()):
c[int(log2(x))] += 1
s += x
if s < n:
print(-1)
continue
i, res = 0, 0
while i < 60:
if (1<<i)&n != 0:
if c[i] > 0:
c[i] -= 1
else:
while i < 60 and c[i] == 0:
i += 1
res += 1
c[i] -= 1
continue
c[i + 1] += c[i] // 2
i += 1
print(res)
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (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())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
string s, t;
inline bool read() {
if(!(cin >> s >> t))
return false;
for(auto &c : s)
c -= 'a';
for(auto &c : t)
c -= 'a';
return true;
}
vector< vector<int> > nxt;
bool calc(const string &a, const string &b) {
vector< vector<int> > dp(sz(a) + 1, vector<int>(sz(b) + 1, INF));
dp[0][0] = 0;
fore(i, 0, sz(a) + 1) fore(j, 0, sz(b) + 1) {
if(dp[i][j] > sz(s))
continue;
int len = dp[i][j];
if(i < sz(a) && nxt[len][a[i]] < INF) {
dp[i + 1][j] = min(dp[i + 1][j], nxt[len][a[i]] + 1);
}
if(j < sz(b) && nxt[len][b[j]] < INF) {
dp[i][j + 1] = min(dp[i][j + 1], nxt[len][b[j]] + 1);
}
}
return dp[sz(a)][sz(b)] < INF;
}
inline void solve() {
nxt.assign(sz(s) + 1, vector<int>(26, INF));
for(int i = sz(s) - 1; i >= 0; i--) {
nxt[i] = nxt[i + 1];
nxt[i][s[i]] = i;
}
for(int i = 0; i < sz(t); i++) {
if(calc(t.substr(0, i), t.substr(i, sz(t)))) {
cout << "YES" << endl;
return;
}
}
cout << "NO" << 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 tc; cin >> tc;
while(tc--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define forr(i, r, l) for (int i = int(r) - 1; i >= int(l); --i)
typedef pair<int, int> pt;
const int M = 310;
const int N = 2000 * 1000 + 13;
int n, m, q;
int a[M][M];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
int p[M * M], rk[M * M];
int getp(int v) {
return p[v] == v ? v : p[v] = getp(p[v]);
}
bool unite(int a, int b) {
a = getp(a); b = getp(b);
if (a == b) return false;
if (rk[a] < rk[b]) swap(a, b);
p[b] = a;
rk[a] += rk[b];
return true;
}
int dif[N];
vector<pt> add[N], del[N];
void recalc(const vector<pt>& ev, int coeff) {
forn(i, n) forn(j, m) a[i][j] = 0;
forn(i, n * m) p[i] = i, rk[i] = 1;
for (auto it : ev) {
int cur = 1;
int x = it.x / m, y = it.x % m;
a[x][y] = 1;
forn(k, 4) {
int nx = x + dx[k];
int ny = y + dy[k];
if (in(nx, ny) && a[nx][ny] == 1)
cur -= unite(nx * m + ny, x * m + y);
}
dif[it.y] += cur * coeff;
}
}
int main() {
scanf("%d%d%d", &n, &m, &q);
int clrs = 1;
forn(i, q) {
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
--x; --y;
if (a[x][y] == c) continue;
clrs = c + 1;
add[c].pb(mp(x * m + y, i));
del[a[x][y]].pb(mp(x * m + y, i));
a[x][y] = c;
}
forn(x, n) forn(y, m)
del[a[x][y]].pb(mp(x * m + y, q));
forn(i, clrs) reverse(all(del[i]));
forn(i, clrs) recalc(add[i], +1);
forn(i, clrs) recalc(del[i], -1);
int cur = 1;
forn(i, q) {
cur += dif[i];
printf("%d\n", cur);
}
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 150043;
typedef pair<long long, long long> func;
func T[4 * N];
bool usedT[4 * N];
void clear(int v, int l, int r)
{
if(!usedT[v]) return;
usedT[v] = false;
T[v] = make_pair(0ll, 0ll);
if(l < r - 1)
{
int m = (l + r) / 2;
clear(v * 2 + 1, l, m);
clear(v * 2 + 2, m, r);
}
}
long long eval(func f, int x)
{
return f.first * x + f.second;
}
long long get(int v, int l, int r, int x)
{
long long ans = eval(T[v], x);
if(l < r - 1)
{
int m = (l + r) / 2;
if(m > x)
ans = max(ans, get(v * 2 + 1, l, m, x));
else
ans = max(ans, get(v * 2 + 2, m, r, x));
}
return ans;
}
void upd(int v, int l, int r, func f)
{
usedT[v] = true;
int m = (l + r) / 2;
bool need_swap = eval(f, m) > eval(T[v], m);
if(need_swap)
swap(T[v], f);
if(l == r - 1)
return;
if(eval(f, l) > eval(T[v], l))
upd(v * 2 + 1, l, m, f);
else
upd(v * 2 + 2, m, r, f);
}
long long ans = 0;
void update_ans(vector<vector<func> > heads, vector<vector<func> > tails)
{
int n = heads.size();
for(int i = 0; i < n; i++)
{
for(auto x : heads[i])
ans = max(ans, get(0, 0, N, x.first) + x.second);
for(auto x : tails[i])
upd(0, 0, N, x);
}
clear(0, 0, N);
}
int a[N];
vector<int> g[N];
int n;
bool used[N];
int siz[N];
void dfs1(int x, int p = -1)
{
if(used[x]) return;
siz[x] = 1;
for(auto to : g[x])
{
if(!used[to] && to != p)
{
dfs1(to, x);
siz[x] += siz[to];
}
}
}
pair<int, int> c;
int S = 0;
void find_centroid(int x, int p = -1)
{
if(used[x]) return;
int mx = 0;
for(auto to : g[x])
{
if(!used[to] && to != p)
{
find_centroid(to, x);
mx = max(mx, siz[to]);
}
}
if(p != -1)
mx = max(mx, S - siz[x]);
c = min(c, make_pair(mx, x));
}
void dfs_heads(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
if(used[v])
return;
cnt++;
curadd += a[v];
cursum += curadd;
sink.push_back(make_pair(cnt, cursum));
for(auto to : g[v])
if(to != p)
dfs_heads(to, v, cnt, cursum, curadd, sink);
}
void dfs_tails(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
if(used[v])
return;
cnt++;
curadd += a[v];
cursum += a[v] * 1ll * cnt;
sink.push_back(make_pair(curadd, cursum));
for(auto to : g[v])
if(to != p)
dfs_tails(to, v, cnt, cursum, curadd, sink);
}
void centroid(int v)
{
if(used[v]) return;
dfs1(v);
S = siz[v];
c = make_pair(int(1e9), -1);
find_centroid(v);
int C = c.second;
used[C] = 1;
vector<vector<func> > heads, tails;
for(auto to : g[C])
if(!used[to])
{
heads.push_back(vector<func>());
dfs_heads(to, C, 1, a[C], a[C], heads.back());
tails.push_back(vector<func>());
dfs_tails(to, C, 0, 0, 0, tails.back());
}
heads.push_back(vector<func>({{1, a[C]}}));
tails.push_back(vector<func>({{0, 0}}));
update_ans(heads, tails);
reverse(heads.begin(), heads.end());
reverse(tails.begin(), tails.end());
update_ans(heads, tails);
for(auto to : g[C])
centroid(to);
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
centroid(0);
printf("%lld\n", ans);
}