Submission #849215

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
849215	2023-09-14T09:23:56 Z	quanlt206	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	1000 ms	34168 KB

jobs

#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 1e5 + 7;

vector<pii> query[N];
vector<int> res[N], ans[N];

int n, m, d;

bool check(int x) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    FOR(i, 1, n) ans[i].clear();
    FOR(i, 1, n) {
        for (auto x : query[i]) pq.push({x.X, x.Y});
        int m = x;
//        cout<<i<<" "<<pq.size()<<"\n";
        while (m > 0 && !pq.empty()) {
            pii tmp = pq.top();
            pq.pop();
            int r = tmp.X, idx = tmp.Y;
            if (r < i) return false;
            ans[i].push_back(idx);
            m--;
        }
    }
    if (!pq.empty()) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>d>>m;
    FOR(i, 1, m) {
        int x;
        cin>>x;
        query[x].push_back({x + d, i});
    }
    int d = 1, c = m, g, result = 0;
//    check(1);
//    exit(0);
    while (d <= c) {
        g = (d + c) >> 1;
        if (check(g)) {
            result = g;
            FOR(i, 1, n) res[i] = ans[i];
            c = g - 1;
        }
        else d = g + 1;
    }
    cout<<result<<"\n";
    FOR(i, 1, n) {
        for (auto x : res[i]) cout<<x<<" "; cout<<0<<"\n";
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:92:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   92 |         for (auto x : res[i]) cout<<x<<" "; cout<<0<<"\n";
      |         ^~~
jobs.cpp:92:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |         for (auto x : res[i]) cout<<x<<" "; cout<<0<<"\n";
      |                                             ^~~~

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	11212 KB	Output is correct
2	Correct	148 ms	11244 KB	Output is correct
3	Correct	150 ms	11228 KB	Output is correct
4	Correct	147 ms	11228 KB	Output is correct
5	Correct	146 ms	11228 KB	Output is correct
6	Correct	147 ms	11216 KB	Output is correct
7	Correct	149 ms	11220 KB	Output is correct
8	Correct	148 ms	11224 KB	Output is correct
9	Correct	123 ms	10616 KB	Output is correct
10	Correct	126 ms	10628 KB	Output is correct
11	Correct	69 ms	10324 KB	Output is correct
12	Correct	236 ms	13476 KB	Output is correct
13	Correct	292 ms	18188 KB	Output is correct
14	Correct	350 ms	22104 KB	Output is correct
15	Correct	437 ms	23216 KB	Output is correct
16	Correct	356 ms	27392 KB	Output is correct
17	Runtime error	560 ms	33648 KB	Memory limit exceeded
18	Execution timed out	1008 ms	32532 KB	Time limit exceeded
19	Execution timed out	1008 ms	34168 KB	Time limit exceeded
20	Runtime error	585 ms	33684 KB	Memory limit exceeded