Submission #939888

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
939888	2024-03-06T22:34:05 Z	lucascgar	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	509 ms	23392 KB

jobs

#include <bits/stdc++.h>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 1e6+10;

int dy[MAXN];

signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int n, d, m;
    cin >> n >> d >> m;

    vector<pii> sc;
    for (int i=1;i<=m;i++){
        cin >> dy[i];
        sc.push_back({dy[i], i});
    }
    sort(sc.begin(), sc.end());

    int in = 0, fi = 1e6, me;
    vector<int> ans;
    while (in<=fi){
        me = (in+fi)/2;

        int ct = 0, dt = 0;
        bool v = 1;
        vector<int> td;
        for (int i=1;i<=n;i++){
            while (ct<sc.size() && sc[ct].first == i) td.push_back(sc[ct++].second);

            for (int j=0;j<me;j++){
                if (dt < td.size()) dt++;
                else break;
            }

            if (dt < td.size() && dy[td[dt]]+d <= i){
                v = 0;
                break;
            }

        }

        if (v){
            fi = me-1;
            ans = td;
        }
        else in = me+1;

    }

    cout << fi+1 << "\n";
    int j = 0;
    for (int i=0;i<n;i++){
        for (int k=0;k<fi+1;k++) if (j < ans.size()) cout << ans[j++] << " ";
        cout << "0\n";
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             while (ct<sc.size() && sc[ct].first == i) td.push_back(sc[ct++].second);
      |                    ~~^~~~~~~~~~
jobs.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 if (dt < td.size()) dt++;
      |                     ~~~^~~~~~~~~~~
jobs.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             if (dt < td.size() && dy[td[dt]]+d <= i){
      |                 ~~~^~~~~~~~~~~
jobs.cpp:70:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int k=0;k<fi+1;k++) if (j < ans.size()) cout << ans[j++] << " ";
      |                                      ~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	483 ms	5076 KB	Output is correct
2	Correct	502 ms	5076 KB	Output is correct
3	Correct	488 ms	5076 KB	Output is correct
4	Correct	491 ms	5076 KB	Output is correct
5	Correct	501 ms	5076 KB	Output is correct
6	Correct	509 ms	5144 KB	Output is correct
7	Correct	479 ms	5080 KB	Output is correct
8	Correct	494 ms	5080 KB	Output is correct
9	Correct	488 ms	5152 KB	Output is correct
10	Correct	454 ms	4904 KB	Output is correct
11	Correct	38 ms	5008 KB	Output is correct
12	Correct	54 ms	7508 KB	Output is correct
13	Correct	85 ms	11000 KB	Output is correct
14	Correct	115 ms	13064 KB	Output is correct
15	Correct	141 ms	13268 KB	Output is correct
16	Correct	175 ms	20508 KB	Output is correct
17	Correct	209 ms	20368 KB	Output is correct
18	Correct	223 ms	22020 KB	Output is correct
19	Correct	333 ms	23392 KB	Output is correct
20	Correct	219 ms	20772 KB	Output is correct