Submission #317120

#	Time	Username	Problem	Language	Result	Execution time	Memory
317120		ant101	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	710 ms	39416 KiB

jobs

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;
 
//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007
 
typedef long long ll;
 
 
ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}
 
ll mul(ll a, ll b) {
    return (a * b)%MOD;
}
 
void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}
 
 
const ll MAXN = 1000010;
 
ll jobs[MAXN];
ll N, M, D;
vector<ll> buckets[100010];
vector<ll> ans[100010];
 
int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
//    ifstream fin;
//    fin.open("in.10");
    cin >> N >> D >> M;
    for (ll i = 0; i<M; i++) {
        cin >> jobs[i];
        buckets[jobs[i]].push_back(i);
    }
    ll L = 1, R = M;
    while (L <= R) {
        for (ll i = 0; i<100010; i++) {
            ans[i].clear();
        }
        ll mid = (L+R)/2;
        queue<ll> q;
        ll bad = false;
        for (ll i = 1; i<=N; i++) {
            for (ll j = 0; j<buckets[i].size(); j++) {
                q.push(buckets[i][j]);
            }
            for (ll j = 0; j<mid; j++) {
                if (q.empty()) {
                    break;
                }
                if (i-jobs[q.front()] > D) {
                    bad = true;
                    break;
                }
                ans[i].push_back(q.front());
                q.pop();
            }
            if (bad) {
                break;
            }
        }
        if (L == R) {
            break;
        }
        if (bad) {
            L = mid+1;
        } else {
            R = mid;
        }
    }
//    vector<ll> list;
//    for (ll i = 1; i<=N; i++) {
//        for (ll j = 0; j<buckets[i].size(); j++) {
//            list.push_back(buckets[i][j]);
//        }
//    }
//    cout << L << "\n";
//    ll cnt = 0;
//    for (ll i = 0; i<list.size(); i++) {
//        if (i != 0 && i%L == 0) {
//            cout << 0 << "\n";
//            cnt++;
//        }
//        cout << 1+list[i] << " ";
//    }
//    cout << "0\n";
    cout << L << "\n";
    for (ll i = 1; i<=N; i++) {
        for (ll j = 0; j<ans[i].size(); j++) {
            cout << ans[i][j]+1 << " ";
        }
        cout << "0\n";
    }
    
    return 0;
}
 
 

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:87:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for (ll j = 0; j<buckets[i].size(); j++) {
      |                            ~^~~~~~~~~~~~~~~~~~
jobs.cpp:132:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (ll j = 0; j<ans[i].size(); j++) {
      |                        ~^~~~~~~~~~~~~~

• Subtask 1: 80 / 100