제출 #480552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
480552		definitelynotmee	Hiring (IOI09_hiring)	C++98	98 / 100	818 ms	48404 KiB

hiring

#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;

inline int midpoint(int l, int r){
    return (l+r)>>1;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, w;
    cin >> n >> w;
    vector<pll> v(n);
    vector<int> o(n), o1(n),o2(n);

    for(int i = 0; i < n; i++){
        cin >> v[i].ff >> v[i].ss;
    } 
    iota(all(o1),0);
    sort(all(o1),[&](int a,int b){
        return v[a].ss < v[b].ss;
    });
    for(int i = 0; i < n; i++){
        o2[o1[i]] = i;
    }
    iota(all(o),0);
    sort(all(o),[&](int a, int b){
        if(v[a].ff*v[b].ss == v[a].ss*v[b].ff)
            return o2[a] < o2[b];
        return v[a].ff*v[b].ss < v[a].ss*v[b].ff;
    });
    vector<pll> tree(4*n);
    function<void(int,int,int,int,int)> update= [&](int id, int l, int r, int q, int val){
        if(l > q || r < q)
            return;
        if(l == r && r == q){
            tree[id] = {val,1};
            return;
        }
        int e = id*2+1;
        int d = id*2+2;
        int m = midpoint(l,r);
        update(e,l,m,q,val);
        update(d,m+1,r,q,val);
        tree[id] = {tree[e].ff + tree[d].ff, tree[e].ss + tree[d].ss};
    };
    struct fraction{
        ll x,y;
        bool operator<(fraction b){
            return x*b.y < y*b.x;
        }
    };
    fraction sobra = {0,1};
    function<int(int,int,int,ll,ll)> bb =[&](int id,int l, int r, ll rest, ll cost)->int{
        if(l==r){
            if(tree[id].ss && tree[id].ff*cost <= rest){
                sobra = {rest-tree[id].ff*cost,cost};
                return 1;
            }
            sobra = {rest,cost};
            return 0;
        }
            
        int e = id*2+1;
        int d = id*2+2;
        int m = midpoint(l,r);
        if(tree[e].ff*cost < rest)
            return bb(d,m+1,r,rest-tree[e].ff*cost,cost)+tree[e].ss;
        return bb(e,l,m,rest,cost);
    };
    pair<int,fraction> resp = {0,{0,1}};
    int respid = 0;
    for(int i = 0; i < n; i++){
        update(0,0,n-1,o2[o[i]],v[o[i]].ss);
        int cur = bb(0,0,n-1,w*v[o[i]].ss,v[o[i]].ff);
        if(resp.ff < cur || (resp.ff == cur && resp.ss < sobra)){
            resp = {cur,sobra},respid = i;
        }
    }
    cout << resp.ff << '\n';
    vector<int> in;
    for(int i = 0; i <= respid; i++){
        in.push_back(o[i]);
    }
    sort(all(in),[&](int a,int b){
        return o2[a] < o2[b];
    });
    for(int i = 0; i < resp.ff; i++){
        cout << in[i] + 1<< '\n';
    }
    return 0;

}

• Subtask 1: 28 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6