oj.uz

답안 #317120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
317120 2020-10-29T03:47:35 Z ant101 Job Scheduling (CEOI12_jobs) C++14
80 / 100
 710 ms 39416 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 9708 KB Output is correct
2 Correct 42 ms 9780 KB Output is correct
3 Correct 39 ms 9712 KB Output is correct
4 Correct 40 ms 9708 KB Output is correct
5 Correct 41 ms 9712 KB Output is correct
6 Correct 40 ms 9712 KB Output is correct
7 Correct 41 ms 9712 KB Output is correct
8 Correct 40 ms 9708 KB Output is correct
9 Correct 49 ms 9080 KB Output is correct
10 Correct 48 ms 9080 KB Output is correct
11 Correct 51 ms 8952 KB Output is correct
12 Correct 100 ms 12768 KB Output is correct
13 Correct 158 ms 18972 KB Output is correct
14 Correct 272 ms 23168 KB Output is correct
15 Correct 325 ms 25516 KB Output is correct
16 Correct 426 ms 31348 KB Output is correct
17 Runtime error 546 ms 39416 KB Memory limit exceeded
18 Runtime error 597 ms 36768 KB Memory limit exceeded
19 Runtime error 710 ms 38648 KB Memory limit exceeded
20 Runtime error 669 ms 39164 KB Memory limit exceeded