Submission #374776

# Submission time Handle Problem Language Result Execution time Memory
374776 2021-03-08T07:00:26 Z ijxjdjd Hiring (IOI09_hiring) C++14
53 / 100
314 ms 34676 KB
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

struct person {
    ll S, Q;
    int 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 int MAXS = 20005;
ll sm[4*MAXS];
ll cnt[4*MAXS];
ll W;
ans updMx(person last) {
    int u = 1;
    int tl = 0;
    int tr = MAXS-1;
    ans res = {0, last.S, last.Q, 0};
    while (tl != tr) {
        int 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) {
        int 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) {
    int u = 1;
    int tl = 0;
    int tr = MAXS-1;
    while (true) {
        int tm = (tl + tr)/2;
        cnt[u]++;
        sm[u] += p.Q;
        if (p.Q <= tm) {
            u = 2*u;
            tr = tm;
        }
        else {
            u = 2*u+1;
            tl = tm+1;
        }
        if (tl == tr) {
            break;
        }
    }
}
int 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;
}
# 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 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Partially correct 2 ms 620 KB Partially correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 4 ms 1132 KB Output is correct
10 Incorrect 3 ms 1132 KB Output isn't correct
11 Correct 4 ms 1260 KB Output is correct
12 Partially correct 4 ms 1004 KB Partially correct
13 Correct 6 ms 1388 KB Output is correct
14 Incorrect 8 ms 1644 KB Output isn't correct
15 Partially correct 9 ms 1900 KB Partially correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Partially correct 1 ms 364 KB Partially correct
3 Correct 1 ms 748 KB Output is correct
4 Partially correct 13 ms 2284 KB Partially correct
5 Incorrect 31 ms 5228 KB Output isn't correct
6 Incorrect 192 ms 21612 KB Output isn't correct
7 Incorrect 227 ms 28268 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 876 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 9452 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 15084 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 31468 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 314 ms 34676 KB Output isn't correct
2 Halted 0 ms 0 KB -