oj.uz

Submission #905005

# Submission time Handle Problem Language Result Execution time Memory
905005 2024-01-12T12:50:45 Z akliu Job Scheduling (CEOI12_jobs) C++11
90 / 100
 1000 ms 20416 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) {
    
    if (m == 2) {
        int ans = 0;
    }
    
    // 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 && q.sz()) {
            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:48:13: warning: unused variable 'ans' [-Wunused-variable]
   48 |         int ans = 0;
      |             ^~~
jobs.cpp:65:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |         while (machines.sz() != m && q.sz()) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:70:31: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |             if (machines.sz() != m) machines.ins(val.day);
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:109: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]
  109 |         while (machines.sz() != l && q.sz()) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:116: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]
  116 |             if (machines.sz() != l) {
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         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 325 ms 7376 KB Output is correct
2 Correct 343 ms 7504 KB Output is correct
3 Correct 346 ms 7516 KB Output is correct
4 Correct 363 ms 7440 KB Output is correct
5 Correct 342 ms 7376 KB Output is correct
6 Correct 365 ms 7504 KB Output is correct
7 Correct 347 ms 7508 KB Output is correct
8 Correct 347 ms 7500 KB Output is correct
9 Correct 171 ms 5544 KB Output is correct
10 Correct 219 ms 5776 KB Output is correct
11 Correct 107 ms 2768 KB Output is correct
12 Correct 327 ms 5884 KB Output is correct
13 Correct 400 ms 8860 KB Output is correct
14 Correct 569 ms 12940 KB Output is correct
15 Correct 563 ms 11624 KB Output is correct
16 Correct 473 ms 16588 KB Output is correct
17 Correct 781 ms 20416 KB Output is correct
18 Execution timed out 1045 ms 11200 KB Time limit exceeded
19 Execution timed out 1060 ms 11792 KB Time limit exceeded
20 Correct 810 ms 19936 KB Output is correct