Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
def maxSum(x):
return x ** 2
def getAns(x):
res = 1
while maxSum(res) < x:
res += 1
return res
def main():
t = int(input())
for i in range(t):
print(getAns(int(input())))
main()
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, a, b;
string s;
cin >> n >> a >> b >> s;
int m = unique(s.begin(), s.end()) - s.begin();
cout << n * a + max(n * b, (m / 2 + 1) * b) << '\n';
}
}
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 long double ld;
typedef pair<li, li> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n;
vector<li> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
li d(const pt &a, const pt &b) {
return abs(a.x - b.x) + abs(a.y - b.y);
}
inline void solve() {
li ans = 0;
fore (i, 0, n) {
fore (j, i, n) {
if (i + 2 <= j) {
bool ok = true;
fore (i1, i, j) fore (i2, i1 + 1, j) {
if (d(pt(a[i1], i1), pt(a[j], j)) == d(pt(a[i1], i1), pt(a[i2], i2)) + d(pt(a[i2], i2), pt(a[j], j)))
ok = false;
}
if (!ok)
break;
}
ans++;
}
}
cout << ans << 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;
}
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())
const int MOD = int(1e9) + 7;
int norm(int a) {
while (a >= MOD)
a -= MOD;
while (a < 0)
a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
while (k > 0) {
if (k & 1)
ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
const int N = 200 * 1000 + 55;
int f[N], inf[N];
void precalc() {
f[0] = inf[0] = 1;
fore (i, 1, N) {
f[i] = mul(f[i - 1], i);
inf[i] = binPow(f[i], MOD - 2);
}
}
int C(int n, int k) {
if (k < 0 || n < k)
return 0;
return mul(f[n], mul(inf[n - k], inf[k]));
}
int n, l, r;
inline bool read() {
if(!(cin >> n >> l >> r))
return false;
return true;
}
inline void solve() {
int half = n / 2;
int st = min(1 - l, r - n);
int ans = mul(st, C(n, half));
if (n & 1)
ans = norm(ans + mul(st, C(n, half + 1)));
for (int k = st + 1; ; k++) {
int lf = max(1, l + k);
int rg = min(n, r - k);
if (rg + 1 - lf < 0)
break;
ans = norm(ans + C(rg + 1 - lf, half - (lf - 1)));
if (n & 1)
ans = norm(ans + C(rg + 1 - lf, half + 1 - (lf - 1)));
}
cout << ans << 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);
precalc();
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
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 n, k;
string s;
bool check(int d){
vector<int> lst(k, n);
vector<vector<int>> pos(n + 1, vector<int>(k, n + 1));
for (int i = n - 1; i >= 0; --i){
if (s[i] != '?'){
lst[s[i] - 'a'] = i;
}
int cur = n;
forn(j, k){
pos[i][j] = (i + d <= cur ? i + d : pos[i + 1][j]);
cur = min(cur, lst[j]);
}
cur = n;
for (int j = k - 1; j >= 0; --j){
if (i + d > cur) pos[i][j] = pos[i + 1][j];
cur = min(cur, lst[j]);
}
}
vector<int> dp(1 << k, n + 1);
dp[0] = 0;
forn(mask, 1 << k) if (dp[mask] < n + 1){
forn(i, k) if (!((mask >> i) & 1))
dp[mask | (1 << i)] = min(dp[mask | (1 << i)], pos[dp[mask]][i]);
}
return dp[(1 << k) - 1] <= n;
}
int main() {
cin >> n >> k;
cin >> s;
int l = 1, r = n;
int res = 0;
while (l <= r){
int m = (l + r) / 2;
if (check(m)){
res = m;
l = m + 1;
}
else{
r = m - 1;
}
}
cout << res << endl;
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int INF = 1e9;
struct edge2{
int u, w;
};
vector<vector<edge2>> g;
struct edge3{
int v, u, w;
};
bool operator <(const edge3 &a, const edge3 &b){
if (a.w != b.w)
return a.w < b.w;
if (min(a.v, a.u) != min(b.v, b.u))
return min(a.v, a.u) < min(b.v, b.u);
return max(a.v, a.u) < max(b.v, b.u);
}
vector<vector<int>> comps;
vector<int> p;
bool unite(int a, int b){
a = p[a], b = p[b];
if (a == b) return false;
if (comps[a].size() < comps[b].size()) swap(a, b);
for (int v : comps[b]){
p[v] = a;
comps[a].push_back(v);
}
comps[b].clear();
return true;
}
vector<int> mn;
void dfs(int v, int p, int d){
mn[v] = d;
for (auto e : g[v]) if (e.u != p)
dfs(e.u, v, max(d, e.w));
}
int main() {
int n, q, s, d;
scanf("%d%d%d%d", &n, &q, &s, &d);
--s;
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<int> idx(a[n - 1] + 1);
forn(i, n) idx[a[i]] = i;
comps.resize(n);
p.resize(n);
forn(i, n) comps[i] = vector<int>(1, i), p[i] = i;
g.resize(n);
set<int> pos(a.begin(), a.end());
int cnt = n;
while (cnt > 1){
vector<edge3> es;
for (const vector<int> &comp : comps) if (!comp.empty()){
for (int i : comp)
pos.erase(a[i]);
edge3 mn = {-1, -1, INF};
for (int i : comp){
for (int dx : {-d, d}){
auto it = pos.lower_bound(a[i] + dx);
if (it != pos.end())
mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)});
if (it != pos.begin()){
--it;
mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)});
}
}
}
for (int i : comp)
pos.insert(a[i]);
assert(mn.v != -1);
es.push_back(mn);
}
for (auto e : es){
if (unite(e.v, e.u)){
--cnt;
g[e.v].push_back({e.u, e.w});
g[e.u].push_back({e.v, e.w});
}
}
}
mn.resize(n);
dfs(s, -1, 0);
forn(_, q){
int i, k;
scanf("%d%d", &i, &k);
--i;
puts(mn[i] <= k ? "Yes" : "No");
}
return 0;
}
Solution 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int INF = 1e9;
struct edge2{
int u, w;
};
vector<vector<edge2>> g;
struct edge3{
int v, u, w;
edge3(){}
edge3(int v, int u, int w) : v(v), u(u), w(w) {
if (v > u) swap(v, u);
}
};
bool operator <(const edge3 &a, const edge3 &b){
if (a.w != b.w)
return a.w < b.w;
if (a.v != b.v)
return a.v < b.v;
return a.u < b.u;
}
vector<int> p, rk;
int getp(int a){
return a == p[a] ? a : p[a] = getp(p[a]);
}
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);
rk[a] += rk[b];
p[b] = a;
return true;
}
vector<int> mn;
void dfs(int v, int p, int d){
mn[v] = d;
for (auto e : g[v]) if (e.u != p)
dfs(e.u, v, max(d, e.w));
}
int main() {
int n, q, s, d;
scanf("%d%d%d%d", &n, &q, &s, &d);
--s;
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
p.resize(n);
rk.resize(n);
forn(i, n) rk[i] = 1, p[i] = i;
g.resize(n);
int cnt = n;
int iter = 0;
while (cnt > 1){
++iter;
vector<edge3> es(n, edge3(-1, -1, INF));
int j, mn1, mn2;
j = 0, mn1 = -1, mn2 = -1;
forn(i, n) getp(i);
forn(i, n){
while (j < n && a[i] - a[j] > d){
if (mn1 == -1 || p[mn1] == p[j])
mn1 = j;
else{
mn2 = mn1;
mn1 = j;
}
++j;
}
if (mn1 != -1 && p[mn1] != p[i]){
es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
}
if (mn2 != -1 && p[mn2] != p[i]){
es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
}
}
j = 0, mn1 = -1, mn2 = -1;
forn(i, n){
while (j < n && a[j] - a[i] <= d){
if (mn1 == -1 || p[mn1] == p[j])
mn1 = j;
else{
mn2 = mn1;
mn1 = j;
}
++j;
}
if (mn1 != -1 && p[mn1] != p[i]){
es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
}
if (mn2 != -1 && p[mn2] != p[i]){
es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
}
}
j = n - 1, mn1 = -1, mn2 = -1;
for (int i = n - 1; i >= 0; --i){
while (j >= 0 && a[j] - a[i] > d){
if (mn1 == -1 || p[mn1] == p[j])
mn1 = j;
else{
mn2 = mn1;
mn1 = j;
}
--j;
}
if (mn1 != -1 && p[mn1] != p[i]){
es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
}
if (mn2 != -1 && p[mn2] != p[i]){
es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
}
}
j = n - 1, mn1 = -1, mn2 = -1;
for (int i = n - 1; i >= 0; --i){
while (j >= 0 && a[i] - a[j] <= d){
if (mn1 == -1 || p[mn1] == p[j])
mn1 = j;
else{
mn2 = mn1;
mn1 = j;
}
--j;
}
if (mn1 != -1 && p[mn1] != p[i]){
es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
}
if (mn2 != -1 && p[mn2] != p[i]){
es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
}
}
for (auto e : es) if (e.v != -1){
if (unite(e.v, e.u)){
--cnt;
g[e.v].push_back({e.u, e.w});
g[e.u].push_back({e.v, e.w});
}
}
}
mn.resize(n);
dfs(s, -1, 0);
forn(_, q){
int i, k;
scanf("%d%d", &i, &k);
--i;
puts(mn[i] <= k ? "Yes" : "No");
}
return 0;
}