Submission #927915

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
927915	2024-02-15T14:03:32 Z	megaminion	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	1000 ms	32928 KB

jobs

#include <bits/stdc++.h>
#define pb push_back
#define ins insert
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define endl '\n'
using namespace std;
using ll = long long;
const int M = 1e6;
const int N = 1e5;

int n, d, m;
int a[M], mp[N+1];
vector<int> v[N+1];
vector<int> p[N+1];

bool ok(int x, bool flag)
{
    bool ret = true;
    multiset<int> s;
    for(int i = 1; i <= n; ++i)
    {
        v[i].clear();
        for(int j = 0; j < mp[i]; ++j)
        {
            s.ins(i);
        }
        for(int j = 0; j < x; ++j)
        {
            if(s.empty()) break;
            ret &= i - *s.begin() <= d;
            if(flag)
            {
                v[i].pb(p[*s.begin()].back());
                p[*s.begin()].pop_back();
            }
            s.erase(s.begin());
        }
    }
    return ret;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>d>>m;
    for(int i = 0; i < m; ++i)
    {
        cin>>a[i];
        mp[a[i]]++;
        p[a[i]].pb(i+1);
    }
    int L = 1, R = 1e7, mid;
    while(L < R)
    {
        mid = L + (R - L) / 2;
        if(ok(mid, false))
        {
            R = mid;
        }
        else
        {
            L = mid+1;
        }
    }
    cout<<L<<endl;
    assert(ok(L, true));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j < sz(v[i]); ++j)
        {
            cout<<v[i][j];
            if(j + 1 != sz(v[i])) cout<<" ";
            else cout<<" 0";
        }
        if(v[i].empty())
        {
            cout<<"0";
        }
        if(i != n) cout<<endl;
    }
    return 0;
}

Subtask #1

80.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	332 ms	12404 KB	Output is correct
2	Correct	336 ms	12376 KB	Output is correct
3	Correct	332 ms	12376 KB	Output is correct
4	Correct	327 ms	12396 KB	Output is correct
5	Correct	332 ms	12380 KB	Output is correct
6	Correct	328 ms	12404 KB	Output is correct
7	Correct	353 ms	12376 KB	Output is correct
8	Correct	339 ms	12240 KB	Output is correct
9	Correct	216 ms	10220 KB	Output is correct
10	Correct	212 ms	10136 KB	Output is correct
11	Correct	165 ms	9044 KB	Output is correct
12	Correct	368 ms	11948 KB	Output is correct
13	Correct	506 ms	17572 KB	Output is correct
14	Correct	566 ms	18000 KB	Output is correct
15	Correct	801 ms	23776 KB	Output is correct
16	Correct	796 ms	26104 KB	Output is correct
17	Execution timed out	1032 ms	31044 KB	Time limit exceeded
18	Execution timed out	1034 ms	21824 KB	Time limit exceeded
19	Execution timed out	1046 ms	26700 KB	Time limit exceeded
20	Execution timed out	1008 ms	32928 KB	Time limit exceeded