Submission #939888

#	Time	Username	Problem	Language	Result	Execution time	Memory
939888		lucascgar	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	509 ms	23392 KiB

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 (stderr)

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 / 100