oj.uz

Submission #374780

# Submission time Handle Problem Language Result Execution time Memory
374780 2021-03-08T07:04:39 Z ijxjdjd Hiring (IOI09_hiring) C++14
100 / 100
 329 ms 39420 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
#define int ll
using namespace std;

using ll = long long;

struct person {
    ll S, Q;
    ll i;
};
struct ans {
    ll T, S, Q;
    ll tot;
};
bool operator<(const person& lhs, const person& rhs){
    return lhs.S*rhs.Q < rhs.S*lhs.Q;
}
bool operator<(const ans& lhs, const ans& rhs) {
    if (lhs.tot != rhs.tot) {
        return lhs.tot > rhs.tot;
    }
    else {
        return lhs.T*lhs.S*rhs.Q < rhs.T*rhs.S*lhs.Q;
    }
}
const ll MAXS = 20005;
ll sm[4*MAXS];
ll cnt[4*MAXS];
ll W;
ans updMx(person last) {
    ll u = 1;
    ll tl = 0;
    ll tr = MAXS-1;
    ans res = {0, last.S, last.Q, 0};
    while (tl != tr) {
        ll tm = (tl + tr)/2;
        if ((res.T+sm[2*u])*res.S <= W*res.Q) {
            res.tot += cnt[2*u];
            res.T += sm[2*u];
            u = 2*u+1;
            tl = tm+1;
        }
        else {
            tr = tm;
            u = 2*u;
        }
    }
    ll low = 0;
    ll high = cnt[u];
    while (low < high) {
        ll mid = (low + high+1)/2;
        if ((res.T + mid*tl)*res.S <= W*res.Q) {
            low = mid;
        }
        else {
            high = mid-1;
        }
    }
    res.T += low*tl;
    res.tot += low;
    return res;
}
void add(person p) {
    ll u = 1;
    ll tl = 0;
    ll tr = MAXS-1;
    while (true) {
        ll tm = (tl + tr)/2;
        cnt[u]++;
        sm[u] += p.Q;
        if (tl == tr) {
            break;
        }
        if (p.Q <= tm) {
            u = 2*u;
            tr = tm;
        }
        else {
            u = 2*u+1;
            tl = tm+1;
        }

    }
}
signed main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N >> W;
	vector<person> per;
	per.resize(N);
	FR(i, N) {
	    per[i].i = i;
        cin >> per[i].S >> per[i].Q;
	}
	sort(all(per));
	vector<pair<ans, int>> pos;
	pos.resize(N);
	for (int i = 0; i < N; i++) {
        add(per[i]);
        pos[i] = {updMx(per[i]), i};
	}
	sort(all(pos));
	sort(per.begin(), per.begin() + pos[0].second+1, [](const person& lhs, const person& rhs) {
        return lhs.Q < rhs.Q;
    });
    cout << pos[0].first.tot << '\n';
	for (int i = 0; i < pos[0].first.tot; i++) {
        cout << per[i].i + 1 << '\n';
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 3 ms 1132 KB Output is correct
9 Correct 4 ms 1644 KB Output is correct
10 Correct 4 ms 1516 KB Output is correct
11 Correct 5 ms 1772 KB Output is correct
12 Correct 4 ms 1132 KB Output is correct
13 Correct 6 ms 1900 KB Output is correct
14 Correct 9 ms 2156 KB Output is correct
15 Correct 10 ms 2284 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 13 ms 2796 KB Output is correct
5 Correct 32 ms 4972 KB Output is correct
6 Correct 197 ms 22636 KB Output is correct
7 Correct 232 ms 28780 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1388 KB Output is correct
2 Correct 1 ms 1260 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1388 KB Output is correct
2 Correct 2 ms 1388 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1388 KB Output is correct
2 Correct 2 ms 1388 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 9836 KB Output is correct
2 Correct 76 ms 10092 KB Output is correct
3 Correct 74 ms 9964 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 15212 KB Output is correct
2 Correct 115 ms 16364 KB Output is correct
3 Correct 119 ms 16468 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 32620 KB Output is correct
2 Correct 281 ms 35436 KB Output is correct
3 Correct 294 ms 35564 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 35692 KB Output is correct
2 Correct 329 ms 39420 KB Output is correct
3 Correct 324 ms 39408 KB Output is correct