Submission #1270375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270375		xqysp	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	446 ms	23476 KiB

jobs

// https://oj.uz/problem/view/CEOI12_jobs

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, D, M;
    cin >> N >> D >> M;
    vector<pair<int,int>> requests;
    requests.resize(M);
    for (int i = 0; i < M; i++) {
        int a;
        cin >> a;
        requests[i]=make_pair(a,i+1);
    }
    sort(requests.begin(), requests.end());
    int left = 1, right = M;
    vector<vector<int>> outputVec;
    while (left <= right) {
        int mid = (left + right) / 2;
        // cout<<mid<<endl;
        // 8 2 12 1 2 4 2 1 3 5 6 2 3 6 4
        // 1 2 4 2 1 3 5 6 2 3 6 4
        // 1,1,2,2,2,3,3,4,4,5,6,6
        int index = 0;
        bool enough = true;
        outputVec.clear();
        outputVec.resize(N);
        for (int i = 1; i <= N; i++) {
            if (index >= M) {
                outputVec[i-1].push_back(0);
                continue;
            }
            for (int j = 0; j < mid; j++) {
                if (index >= M) {
                    break;
                }
                if (requests[index].first > i + D) {
                    enough = false;
                    break;
                }
                if (requests[index].first > i) {
                    break;
                }
                outputVec[i-1].push_back(requests[index].second);
                // cout<<"*"<<i-1<<endl;
                index++;
            }
            if (enough == false) {
                break;
            }
            outputVec[i-1].push_back(0);
        }
        if(index<M){
            enough=false;
        }
        if (enough == true) {
            right = mid-1;
        } else {
            left = mid + 1;
        }
    }
    cout << left<<endl;
    //output

    for(int i = 0; i< N;i++){
        for(auto num: outputVec[i]){
            cout<<num<<" ";
        }
        cout<<endl;
    }
    return 0;
}

• Subtask 1: 0 / 100