codeforce div 2

COFO::Round 610

cofo round

COFO::Round #610 ( div 2 )

Problem A : Temporarily unavailable

Point

Design(x)

Big O(time)

Code(x)

#include<bits/stdc++.h>
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
typedef long long ll;
const ll SHIFTs = 10000 * 10000;
using namespace std;

void process(){
    ll a, b, c, r; cin >> a >> b >> c >> r;
    if(a > b) swap(a, b);
    a += SHIFTs, b += SHIFTs, c += SHIFTs;
    ll len = b - a;
    if(c <= a){
        ll gap =  (c + r) - a;
        if(gap > 0) len = max((ll)0, len-gap);
    }else if( c >= b){
        ll gap = b - (c - r);
        if(gap > 0) len = max((ll)0,len-gap);
    }else{
        ll le = c-r, ri = c+r;
        len = max((ll)0, le-a) + max((ll)0, b-ri);
    }
    cout << len << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    rep(i, 1, tc+1){
        process();
    }
    return 0;
}

Problem B1 : K for the Price of One(Easy version)

Point

Design(x)

Big O(time)

Code(x)

#include<bits/stdc++.h>
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
typedef long long ll;
const int MAXN = 2 * 100 * 1000 + 1;
using namespace std;

int n, coin, k, ans;
int a[MAXN];
void solve(int *x, int sz, int money){
    int ret = (sz == n ? 0 : 1);
    rep(i, 0, sz-1){
        if(x[i+1] <= money){
            money -= x[i+1];
            ret += 2;
            i += 1;
        }else if(x[i] <= money){
            money -= x[i];
            ret += 1;
        }else break;
    }
    ans = max(ans, ret);
}
void process(){
    ans = 0;
    cin >> n >> coin >> k;
    rep(i, 0, n) cin >> a[i];
    sort(a, a+n);
    solve(a, n, coin);
    if(coin >= a[0]) solve(a+1, n-1, coin-a[0]);
    cout << ans << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    rep(i, 1, tc+1){
        process();
    }
    return 0;
}

Problem B2 : K for the Price of One ( Hard version )

Point

Design(x)

Big O(time)

Code(x)

#include<bits/stdc++.h>
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
typedef long long ll;
const int MAXN = 2 * 100 * 1000 + 1;
using namespace std;

vector<int> vec;
int n, coin, k, ans;
int a[MAXN];
ll psum[MAXN];
int bs(int st, int en, int money, int shifts){
    int bu = st - 1, ret = 0;
    int mid = 0;
    while( st <= en ){
        mid = (st + en) / 2;
        if(psum[mid+shifts] - psum[bu+shifts] <= 1LL *money){
            st = mid+1;
            ret = max(ret, mid - bu);
        }else{
            en = mid-1;
        }
    }
    return ret;
}
void solve(int *x, int sz, int money, int cnt){
    int shifts = cnt;
    rep(i, 0, sz){
        if(i+k-1 < sz && x[i+k-1] <= money){
            money -= x[i+k-1];
            cnt += k;
            i += (k-1);
        }
        else{
            if(i == 0){
                if(x[i] <= money) cnt++;
            }else{
                int ret = bs(i, sz-1, money, shifts);
                cnt += ret;
            }
            break;
        }
    }
    ans = max(ans, cnt);
}
void process(){
    ans = 0;
    cin >> n >> coin >> k;
    rep(i, 0, n) cin >> a[i];
    sort(a, a+n);
    psum[0] = a[0];
    rep(i, 1, n) psum[i] = psum[i-1] + a[i];
    for(int i = 0; i < k; i++){
        if(i == 0){ solve(a + i, n - i, coin, i); continue; }
        if(1LL * coin >= psum[i-1]) solve(a + i, n - i, (int)(1LL * coin - psum[i-1]), i);
        else break;
    }
    vec.pb(ans);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    rep(i, 1, tc+1){
        process();
    }
    rep(i, 0, vec.size()) cout << vec[i] << endl;
    return 0;
}

Problem C : Petya and Exam

Point

Design(x)

Big O(time)

Big O(memory)

Code(x)

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
const int MAXN = 2 * 100 * 1000 + 1;
typedef long long ll;
using namespace std;

int n, T, a, b;
ll allA, allB;
int hard[MAXN];
vector<pair<ll, ll> > mNh;
void input(){
	// init
	allA = allB = 0;
	mNh.clear();

	cin >> n >> T >> a >> b;
	rep(i, 0, n){
		cin >> hard[i];
		if(hard[i]) allB++;
		else allA++;
	}
	rep(i, 0, n){
		int x; cin >> x;
		mNh.pb({x, hard[i]});
	}
	mNh.pb({T+1, 0});
	sort(mNh.begin(), mNh.end());
}
void process(){
	input();
	ll cntA = 0, cntB = 0, ans = 0;
	rep(i, 0, n+1){
		ll mandatory = cntA * a + cntB * b;
		ll leftT = mNh[i].first - 1 - mandatory;
		if(leftT>=0){
			int ableA = min(allA - cntA, leftT/a);
			leftT -= a * ableA;
			int ableB = min(allB - cntB, leftT/b);
			leftT -= b * ableB;
			ans = max(ans, cntA + cntB + ableA + ableB);
		}
		int l = i;
		while(l < (int)mNh.size() && mNh[i].first == mNh[l].first){
			if(mNh[l].second) cntB++;
			else cntA++;
			l++;
		}
		i = l-1;
	}
	cout << ans << endl;
}
int main(){
	//freopen("readme.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    rep(i, 1, tc+1){
        process();
	}
    return 0;
}