Submission #944396

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
944396	2024-03-12T16:49:23 Z	slumio	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	330 ms	25268 KB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ull = unsigned long long;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*I liked you once but not anymore now*/

bool sea(int n, int m, int d, vector<pair<int, int>> q, int mid)
{

    for (int i = 1; i <= n; i++)
    {
        int cnt = mid;
        while (!q.empty() && --cnt >=0)
        {
            if (i-q.back().first>=0&&i-q.back().first <= d)
                q.pop_back();
            else
                break;
        }
    }

    return q.empty();
}

void printans(int n, int m, int d, vector<pair<int, int>> q, int mid)
{  
    
    for (int i = 1; i <= n; i++)
    {
        int cnt = mid;
        while (!q.empty() && --cnt>=0)
        {
            if (i-q.back().first>=0&&i-q.back().first <= d)
               { cout<<q.back().second<<" ";q.pop_back();}
            else
                break;
        }
        cout<<0<<endl;
    }

    
}
void solve()
{
    int n, d, m;
    cin >> n >> d >> m;

    vector<pair<int, int>> a;
    for (int i = 1; i <= m; i++)
    {
        int pp;
        cin >> pp;
        a.push_back(pair(pp, i));
    }

    sort(a.begin(), a.end(), [&](const pair<int, int> &aa, const pair<int, int> &bb)
         {
             if (aa.first != bb.first)
                 return aa.first > bb.first;
             else
                 return bb.second < aa.second;
         });

         //for(auto &[x,y]:a)cout<<x<<" "<<y<<endl;

    int ans = 1e8;
    int low = 1;
    int high = 1e7, mid;
    for (int i = 0; i <30 && low <= high; i++)
    {
        if (low <= high)
        {
            mid = (high + low) / 2;
            if (sea(n, m, d, a, mid))
            {
                ans = min(mid, ans);
                high = mid;
            }
            else
                low = mid;
        }
    }

    cout << ans << endl;
    printans(n, m, d, a,ans);

    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    solve();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2756 KB	Output is correct
2	Correct	28 ms	3184 KB	Output is correct
3	Correct	27 ms	2760 KB	Output is correct
4	Correct	36 ms	2760 KB	Output is correct
5	Correct	27 ms	2760 KB	Output is correct
6	Correct	35 ms	2760 KB	Output is correct
7	Correct	27 ms	2760 KB	Output is correct
8	Correct	27 ms	2756 KB	Output is correct
9	Correct	153 ms	2888 KB	Output is correct
10	Correct	157 ms	3256 KB	Output is correct
11	Correct	25 ms	2972 KB	Output is correct
12	Correct	50 ms	5424 KB	Output is correct
13	Correct	75 ms	9880 KB	Output is correct
14	Correct	111 ms	11132 KB	Output is correct
15	Correct	125 ms	13400 KB	Output is correct
16	Correct	157 ms	17244 KB	Output is correct
17	Correct	193 ms	21316 KB	Output is correct
18	Correct	229 ms	22328 KB	Output is correct
19	Correct	330 ms	25268 KB	Output is correct
20	Correct	196 ms	21312 KB	Output is correct