제출 #239271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239271		ant101	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	689 ms	39220 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;
}

컴파일 시 표준 에러 (stderr) 메시지

jobs.cpp: In function 'int main()':
jobs.cpp:87:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (ll j = 0; j<buckets[i].size(); j++) {
                            ~^~~~~~~~~~~~~~~~~~
jobs.cpp:132:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll j = 0; j<ans[i].size(); j++) {
                        ~^~~~~~~~~~~~~~

• Subtask 1: 80 / 100