Submission #711371

#	Time	Username	Problem	Language	Result	Execution time	Memory
711371		asteilind	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	1082 ms	24436 KiB

jobs

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <set>
#include <numeric>
#include <bitset>
#include <climits>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define ll long long
//#define MOD 1000000007
using namespace std;
void setIO(string name = "") { // name is nonempty for USACO file I/O
    ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output
    if(name.length()){
        freopen((name+".in").c_str(), "r", stdin); // see Input & Output
        freopen((name+".out").c_str(), "w", stdout);
    }
}
void solve()
{
    int N,D,M; cin >> N >> D >> M;
    map<int,vector<int>> job;
    forn(i,M)
    {
        int day; cin >> day;
        job[day].push_back(i+1);
    }
    int i=0;
    int j=1e9;
    vector<vector<int>> ans(N);
    int min_machine = 1e9;
    while (i <= j)
    {
        int mid = (i+j)/2;
        vector<vector<int>> temp(N);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        bool flag = true;
        for (int day=1; N>=day ; day++)
        {
            for (auto x: job[day])
            {
                pq.push({day+D,x});
            }
            for (int a=0; mid>a && !pq.empty(); a++)
            {
                auto [dy,indx] = pq.top();
                temp[day-1].push_back(indx);
                pq.pop();
            }
            if (!pq.empty() && pq.top().first <= day)
            {
                flag = false;
                break;
            }
        }
        if (flag && pq.empty())
        {
            min_machine = mid;
            j = mid-1;
            ans = temp;
        }
        else i = mid+1;
    }
    cout << min_machine << endl;
    for (int i=0 ; N>i ; i++)
    {
        for (int j=0; ans[i].size()>j ; j++)
        {
            cout << ans[i][j] << ' ';
        }
        cout << 0 << endl;
    }
}
int main()
{
    setIO("");
    solve();
}

Compilation message (stderr)

jobs.cpp: In function 'void solve()':
jobs.cpp:75:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         for (int j=0; ans[i].size()>j ; j++)
      |                       ~~~~~~~~~~~~~^~
jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen((name+".in").c_str(), "r", stdin); // see Input & Output
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 75 / 100