oj.uz

Submission #739580

# Submission time Handle Problem Language Result Execution time Memory
739580 2023-05-10T17:20:46 Z Dan4Life Hiring (IOI09_hiring) C++17
14 / 100
 640 ms 41488 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN = (int)5e5+10;
const int mxC = (int)20010;
const int LINF = (int)1e18;
int n, W;
int S[mxN], Q[mxN];
int segTree[2*mxN], total[2*mxN];

void upd(int x, int v, int p=0, int l=1, int r=mxC){
    if(l==r){ segTree[p]+=v*l; total[p]+=v; return; }
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(x<=mid) upd(x,v,p+1,l,mid);
    else upd(x,v,rp,mid+1,r);
    segTree[p] = segTree[p+1]+segTree[rp];
    total[p] = total[p+1]+total[rp];
}

int findNum(int x, int p=0, int l=1, int r=mxC){
    if(l==r){
        int L = 0, R = total[p];
        while(L<R){
            int mid = (L+R+1)/2;
            if(mid*l<=x)L=mid;
            else R=mid-1;
        }
        return L;
    }
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(segTree[p+1]==x) return total[p+1];
    if(segTree[p+1]>x) return findNum(x,p+1,l,mid);
    return total[p+1]+findNum(x-segTree[p+1],rp,mid+1,r);
}

int findSum(int x, int p=0, int l=1, int r=mxC){
    if(l==r) return x*l;
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(total[p+1]==x) return segTree[p+1];
    if(total[p+1]>x) return findSum(x,p+1,l,mid);
    return segTree[p+1]+findSum(x-total[p+1],rp,mid+1,r);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> W;
    for(int i = 0; i < n; i++) cin >> S[i] >> Q[i];
    vector<int> ord(n,0); iota(all(ord),0);
    sort(all(ord),[&](int i, int j){
        return S[i]*Q[j] > S[j]*Q[i];
    });
    for(auto i : ord) upd(Q[i],1);
    int num = 0, saved = 0, ind=-1;
    for(auto i : ord){
        upd(Q[i],-1);
        int tot = (W*Q[i])/S[i]-1;
        int curNum = findNum(tot)+1;
        int curSaved = tot-findSum(curNum-1)-Q[i];
        if(num<curNum) num=curNum, saved = curSaved,ind=i;
        else if(num==curNum and saved<curSaved) num=curNum,saved=curSaved,ind=i;
    }
    vector<int> v;
    multiset<pair<int,int>> S;
    for(auto i : ord){
        if(i==ind){
            reverse(all(ord));
            for(auto j : ord){
                S.insert({Q[j],j});
                if(j==ind) break;
            }
            int xd = num;
            while(xd--){
                v.pb(S.begin()->second);
                S.erase(S.begin());
            }
            break;
        }
    }
    cout << num << "\n";
    for(auto u : v) cout << u+1 << "\n";
}

Subtask #1
10.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Correct 3 ms 1108 KB Output is correct
7 Incorrect 2 ms 468 KB Output isn't correct
8 Incorrect 2 ms 724 KB Output isn't correct
9 Correct 5 ms 1236 KB Output is correct
10 Incorrect 5 ms 1108 KB Output isn't correct
11 Correct 7 ms 1364 KB Output is correct
12 Incorrect 6 ms 1108 KB Output isn't correct
13 Incorrect 7 ms 1320 KB Output isn't correct
14 Correct 12 ms 1944 KB Output is correct
15 Incorrect 11 ms 1876 KB Output isn't correct

Subtask #2
4.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 852 KB Output isn't correct
4 Incorrect 15 ms 2120 KB Output isn't correct
5 Incorrect 34 ms 3164 KB Output isn't correct
6 Incorrect 312 ms 22560 KB Output isn't correct
7 Incorrect 453 ms 33004 KB Output isn't correct

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Incorrect 1 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Incorrect 2 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Incorrect 2 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 10248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 17744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 34976 KB Output is correct
2 Incorrect 486 ms 35036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 41488 KB Output is correct
2 Incorrect 640 ms 41356 KB Output isn't correct
3 Halted 0 ms 0 KB -