Codeforces 1251 #Codeforces

1251B.cpp

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

const int maxn = 200 + 10;

char str[60];

void solve(){
    int n, len, even_bad = 0, odd=0;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> str;
        len = strlen(str);
        if(len % 2 == 1) {
            odd++;
            continue;
        }

        int cnt = 0;
        for(int j=0; j<len; j++) if(str[j]=='0') cnt++;
        if(cnt % 2 == 1) even_bad ++;
    }
    cout << (n - (odd==0?(even_bad % 2):0)) << '\n';
}

signed main(){
    Android;
    int t;
    cin >> t;
    while(t--)
        solve();
}

1251C.cpp

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

const int maxn = 3e5 + 10;

int next_p[maxn];
char str[maxn];
int ans[maxn];

void solve(){
    cin >> str;
    int len = strlen(str);
    for(int i=0; i<len; i++) str[i] -= '0';
    str[len] = 127;
    next_p[len-1] = len-1;
    for(int i=len-2; i>=0; i--){
        if(str[i+1]%2==str[i]%2) next_p[i] = next_p[i+1];
        else next_p[i] = i;
    }
    int odd, even, ans_len=0;
    for(odd = 0; odd < len && str[odd]%2!=1; odd++);
    for(even = 0; even < len && str[even]%2!=0; even++);
    while(ans_len < len){
        // cerr << "odd " << odd << " even " << even << endl;
        if(str[odd] < str[even]){
            ans[ans_len++] = str[odd++];
        }else{
            ans[ans_len++] = str[even++];
        }
        if(odd != len && str[odd] % 2 == 0) odd = next_p[odd] + 1;
        if(even != len && str[even] % 2 == 1) even = next_p[even] + 1;
    }
    for(int i=0; i<len; i++){
        cout << ans[i];
    }
    cout << '\n';
}

signed main(){
    Android;
    int t;
    cin >> t;
    while(t--) solve();
}

1251D.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 = 3e5 + 10;

ll n, s;
pair<int, int> employee[maxn];

bool judge(int median){
    ll sum = 0, smaller = 0, greater = 0;
    int k = n / 2;
    vector<int> que;
    for(int i=0; i<n; i++){
        if(employee[i].second < median){
            sum += employee[i].first;
            smaller ++;
        }else if(employee[i].first > median){
            sum += employee[i].first;
            greater ++;
        }else{ 
            que.push_back(employee[i].first);
        }
    }
    if (que.size() + smaller < k + 1) return true;
    if (que.size() + greater < k + 1) return false;
    ll needed = max(0ll, k - smaller);
    for(int i=0; i < needed; i++) sum += que[i];
    sum += 1ll * median * (que.size() - needed);
    // cout << median << " " << sum << endl;
    return sum <= s;
}

void solve(){
    cin >> n >> s;
    int val_cnt = 0;
    for(int i=0; i<n; i++)
        cin >> employee[i].first >> employee[i].second;
    sort(employee, employee + n);

    int l = 0, r = 1e9 + 1, ans;
    while(l < r){
        int mid = (l + r) >> 1;
        if(judge(mid)){
            ans = mid;
            l = mid + 1;
        }else r = mid;
    }
    cout << ans << '\n';
}

signed main(){
    Android;
    int t;
    cin >> t;
    while(t--) solve();
}