oj.uz

Submission #905038

# Submission time Handle Problem Language Result Execution time Memory
905038 2024-01-12T13:14:24 Z akliu Job Scheduling (CEOI12_jobs) C++11
90 / 100
 1000 ms 18072 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
 
// scary demonic thing
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

struct g {
    int day, n;
    bool operator<(const g &y) {
        if (day != y.day) return day < y.day;
    }
};
 
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:63:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         while (machines.sz() != m) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:69:31: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |             if (machines.sz() != m) machines.ins(val.day);
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp: In function 'void solve()':
jobs.cpp:108: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]
  108 |         while (machines.sz() != l && q.sz()) {
      |                ~~~~~~~~~~~~~~^~~~
jobs.cpp:115: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]
  115 |             if (machines.sz() != l) {
      |                 ~~~~~~~~~~~~~~^~~~
jobs.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In member function 'bool g::operator<(const g&)':
jobs.cpp:42:5: warning: control reaches end of non-void function [-Wreturn-type]
   42 |     }
      |     ^

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 7144 KB Output is correct
2 Correct 298 ms 7204 KB Output is correct
3 Correct 285 ms 7004 KB Output is correct
4 Correct 304 ms 7204 KB Output is correct
5 Correct 292 ms 7088 KB Output is correct
6 Correct 331 ms 7204 KB Output is correct
7 Correct 308 ms 7372 KB Output is correct
8 Correct 325 ms 7376 KB Output is correct
9 Correct 151 ms 5272 KB Output is correct
10 Correct 215 ms 5516 KB Output is correct
11 Correct 104 ms 2252 KB Output is correct
12 Correct 299 ms 5060 KB Output is correct
13 Correct 365 ms 6844 KB Output is correct
14 Correct 515 ms 10684 KB Output is correct
15 Correct 530 ms 9616 KB Output is correct
16 Correct 496 ms 12032 KB Output is correct
17 Correct 748 ms 18072 KB Output is correct
18 Execution timed out 1071 ms 9736 KB Time limit exceeded
19 Execution timed out 1058 ms 13572 KB Time limit exceeded
20 Correct 742 ms 16484 KB Output is correct