Codeforces 1244 #Codeforces

1244B.py

def main():
    n = int(input())
    bins = input()
    lmost, rmost = -1, -1
    for i in range(n):
        if bins[i] == '1':
            rmost = i
            if lmost == -1:
                lmost = i
    if lmost == -1:
        print(n)
    else:
        print(max(2 * (rmost + 1), 2 * (n - lmost)))

kase = int(input())
for _ in range(kase):
    main()

1244C.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

ll n, p, w, d;

ll exgcd(ll a, ll b, ll & x, ll & y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y), tmp = x;
    x = y, y = tmp - (a / b) * y;
    return d;
}

void solve(){
    // 求p = b
    cin >> n >> p >> w >> d;
    ll x, y, gcd;
    gcd = exgcd(w, d, x, y);
    if (p % gcd != 0){
        cout << -1 << '\n';
        return;
    }
    // 求wx + dy = p的一组解
    ll t = p / gcd;
    // 求最小整数解
    ll mod = w / gcd;
    y = (((y % mod) + mod) % mod * (t % mod)) % mod;
    x = (p - y * d) / w;

    if(x + y <= n && x >= 0 && y >= 0){
        cout << x << ' ' << y << ' ' << (n - x - y) << '\n';
    }else{
        cout << -1 << '\n';
    }
}

signed main(){
    Android;
    solve();
}

1244E.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 1000;

ll val[maxn], sum[maxn] = {0};
ll n, k;

ll get_maxium(ll k){
    ll l = 0, r = val[n], mid;
    while(l <= r){
        mid = (l + r)>>1;
        int idx = lower_bound(val + 1, val + 1 + n, mid) - val;
        ll cost = sum[n] - sum[idx - 1] - (mid * (n - idx + 1));
        if(cost > k) l = mid + 1;
        else r = mid - 1;
    }
    return r + 1;
}

ll get_minimum(ll k){
    ll l = 0, r = val[n], mid;
    while(l <= r){
        mid = (l + r)>>1;
        int idx = lower_bound(val + 1, val + 1 + n, mid) - val - 1;
        ll cost = mid * idx - sum[idx];
        if(cost > k) r = mid - 1;
        else l = mid + 1;
    }
    return l - 1;
}

void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> val[i];
    sort(val + 1, val + 1 + n);
    for(int i=1; i<=n; i++) sum[i] = sum[i-1] + val[i];

    ll ans = val[n] - val[1];

    // fix the minimum
    for(int i=1; i<=n && i * val[i] - sum[i] <= k; i++){
        ll op_remained = k - (i * val[i] - sum[i]);
        ans = min(ans, max(0ll, get_maxium(op_remained) - val[i]));
    }
    // fix the maximum
    for(int i=n; i>=1; i--){
        ll op_needed = sum[n] - sum[i-1] - (val[i] * (n - i + 1));
        if(op_needed > k) break;
        ll op_remained = k - op_needed;
        ans = min(ans, max(0ll, val[i] - get_minimum(op_remained)));
    }
    cout << ans << '\n';
}

signed main(){
    Android;
    solve();
}