oj.uz

Submission #905012

# Submission time Handle Problem Language Result Execution time Memory
905012 2024-01-12T12:55:31 Z akliu Job Scheduling (CEOI12_jobs) C++11
90 / 100
 1000 ms 17960 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
void fastio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
 
void open(string filename) {
    fastio();
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}
 
typedef long long ll;
#define vll vector<ll>
#define vint vector<int>
#define vbool vector<bool>
#define vpii vector<pii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define ins(x) insert(x)
#define sz() size()
#define lb() lower_bound()
#define ub() upper_bound()
#define rsz resize
#define se second
#define fi first
#define cont continue
 
struct g {
    int day, n;
    bool operator<(const g &y) {
        if (day != y.day) return day < y.day;
        return n < y.n;
    }
};

int N, D, M;
vector<g> v;

bool check(int m) {
    // Iterate to check if the minimum is valid
    multiset<int> machines;
    multiset<int> q;
    int d = 0;
    auto it = v.begin();
    g val = *it;
    while (d != N + 1) {
        if (q.sz()) {
            if (d - *(q.begin()) > D) {
                return false;
            }
        }
        machines.clear();
        val = *it;
        while (machines.sz() != m) {
            if (!q.sz()) break;
            machines.ins(*(q.begin()));
            q.erase(q.begin());
        }
        while (val.day == d) {
            if (machines.sz() != m) machines.ins(val.day);
            else q.ins(val.day);
            ++it;
            if (it == v.end()) break;
            val = *it;
        }
        ++d;
    }
    return true;
}

void solve() {
    // Input
    cin >> N >> D >> M;
    for (int i = 0; i < M; ++i) {
        int a; cin >> a;
        v.pb({a, i + 1});
    }
    sort(v.begin(), v.end());

    // Binary search
    int l = 1, r = 1e6, m;
    while (l < r) {
        m = (l + r) / 2;
        if (check(m)) r = m;
        else l = m + 1;
    }
    cout << l << "\n";

    // Iterate once more with the correct minimum
    vector<vint> ans(N + 1);
    multiset<pii> machines;
    multiset<pii> q;
    int d = 0;
    auto it = v.begin();
    g val = *it;
    while (d != N + 1) {
        machines.clear();
        val = *it;
        while (machines.sz() != l && q.sz()) {
            pii valQ = *(q.begin());
            machines.ins(mp(valQ.fi, valQ.se));
            q.erase(q.begin());
        }
        while (val.day == d) {
            val = *it;
            if (machines.sz() != l) {
                machines.ins(mp(val.day, val.n));
            }
            else q.ins(mp(val.day, val.n));
            ++it;
            if (it == v.end()) break;
        }
        for (auto &x : machines) {
            ans[d].pb(x.se);
        }
        ++d;
    }

    // Output
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < ans[i].sz(); ++j) {
            cout << ans[i][j] << " ";
        }
        cout << "0\n";
    }
}
 
int main() {
    fastio();
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
 
    return 0;
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:60:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         while (machines.sz() != m) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:66:31: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |             if (machines.sz() != m) machines.ins(val.day);
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:105:30: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |         while (machines.sz() != l && q.sz()) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:112:31: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |             if (machines.sz() != l) {
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for (int j = 0; j < ans[i].sz(); ++j) {
      |                           ^
jobs.cpp: In function 'void open(std::string)':
jobs.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 7204 KB Output is correct
2 Correct 330 ms 7132 KB Output is correct
3 Correct 372 ms 7368 KB Output is correct
4 Correct 332 ms 7212 KB Output is correct
5 Correct 376 ms 7216 KB Output is correct
6 Correct 342 ms 7208 KB Output is correct
7 Correct 339 ms 7200 KB Output is correct
8 Correct 339 ms 7376 KB Output is correct
9 Correct 179 ms 5280 KB Output is correct
10 Correct 222 ms 5580 KB Output is correct
11 Correct 103 ms 2144 KB Output is correct
12 Correct 331 ms 5212 KB Output is correct
13 Correct 391 ms 7360 KB Output is correct
14 Correct 556 ms 11592 KB Output is correct
15 Correct 564 ms 9628 KB Output is correct
16 Correct 477 ms 13956 KB Output is correct
17 Correct 768 ms 17960 KB Output is correct
18 Execution timed out 1034 ms 10184 KB Time limit exceeded
19 Execution timed out 1038 ms 10428 KB Time limit exceeded
20 Correct 769 ms 15900 KB Output is correct