oj.uz

답안 #228690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
228690 2020-05-02T11:00:19 Z osaaateiasavtnl Hiring (IOI09_hiring) C++14
100 / 100
 492 ms 58108 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 5e5 + 7;
int n, W;
struct Chel {
    int s, q, i;
} a[N];  
bool comp(Chel a, Chel b) {
    //return (a.s/a.q) < (b.s/b.q);
    return a.s * b.q < b.s * a.q;
}   
bool compq(int i, int j) {
    return a[i].q < a[j].q;
}   
bool ls(ii a, ii b) {
    return a.f * b.s < b.f * a.s;
}

struct Tree {
int cnt[N << 2], sum[N << 2];
void relax(int v) {
    sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
    cnt[v] = cnt[v * 2 + 1] + cnt[v * 2 + 2];
}   
void add(int v, int tl, int tr, int p, int x) {
    if (tl == tr) {
        sum[v] += x;
        ++cnt[v];
        return;
    }
    int tm = (tl + tr) >> 1;
    if (p <= tm)
        add(v * 2 + 1, tl, tm, p, x);
    else
        add(v * 2 + 2, tm + 1, tr, p, x);
    relax(v);                                     
}   
ii get(int v, int tl, int tr, int W, int f) {
    if (tl == tr) {
        if (sum[v] * f > W)
            return mp(0, 0);
        else
            return mp(sum[v], cnt[v]);
    }   
    int tm = (tl + tr) >> 1;
    if (sum[v * 2 + 1] * f >= W) {
        return get(v * 2 + 1, tl, tm, W, f);
    }
    else {
        W -= sum[v * 2 + 1] * f;
        ii ans = get(v * 2 + 2, tm + 1, tr, W, f);
        ans.f += sum[v * 2 + 1];
        ans.s += cnt[v * 2 + 1];
        return ans;
    }                       
}   
} d;

int posq[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> W;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].s >> a[i].q;
        a[i].i = i;
    }   
    sort(a, a + n, comp);

    vector <ii> t;
    for (int i = 0; i < n; ++i)
        t.app(mp(a[i].q, i));
    sort(all(t));
    for (int i = 0; i < n; ++i)
        posq[t[i].s] = i + 1;

    int ans = 0;
    ii pay = {0, 1};
    int ans_i = -1;
    for (int i = 0; i < n; ++i) {
        /*
        used[posq[i]] = 1;
        */
        d.add(0, 0, n, posq[i], a[i].q);

        int sum, k;
        tie(sum, k) = d.get(0, 0, n, W * a[i].q, a[i].s);
        ii np = mp(sum * a[i].s, a[i].q);
        if (k > ans || (k == ans && ls(np, pay))) {
            ans = k;
            pay = np;
            ans_i = i;
        }

        /*
        int sum = 0, k = 0;
        for (int j = 1; j <= n; ++j) {
            if (used[j]) {
                sum += t[j - 1].f;
                ++k;

                if (sum * a[i].s <= W * a[i].q) {
                    ii np = mp(sum * a[i].s, a[i].q);
                    if (k > ans || (k == ans && ls(np, pay))) {
                        ans = k;
                        pay = np;
                        ans_i = i;
                    }
                }   

            }   
        }
        */  
    }
    cout << ans << endl;

    if (ans > 0) {
    vector <ii> t;
    for (int i = 0; i <= ans_i; ++i) {
        t.app(mp(a[i].q, a[i].i));
    }       
    sort(all(t));
    for (int i = 0; i < ans; ++i)
        cout << t[i].s + 1 << ' ';
    cout << endl;           
    }   

}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 8 ms 896 KB Output is correct
10 Correct 8 ms 1024 KB Output is correct
11 Correct 9 ms 1152 KB Output is correct
12 Correct 9 ms 1200 KB Output is correct
13 Correct 11 ms 1408 KB Output is correct
14 Correct 13 ms 1920 KB Output is correct
15 Correct 16 ms 1920 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 19 ms 2684 KB Output is correct
5 Correct 46 ms 8172 KB Output is correct
6 Correct 306 ms 38868 KB Output is correct
7 Correct 330 ms 47960 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 13032 KB Output is correct
2 Correct 106 ms 14140 KB Output is correct
3 Correct 108 ms 14056 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 24160 KB Output is correct
2 Correct 169 ms 26132 KB Output is correct
3 Correct 166 ms 26188 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 427 ms 50260 KB Output is correct
2 Correct 421 ms 55128 KB Output is correct
3 Correct 420 ms 55088 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 490 ms 52560 KB Output is correct
2 Correct 488 ms 57820 KB Output is correct
3 Correct 492 ms 58108 KB Output is correct