Submission #1109817

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109817	2024-11-07T17:16:57 Z	MrPavlito	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	389 ms	34376 KB

jobs

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n,d,m;
vector<pii> niz;
vector<pii> kopija;
vector<pii> resenje;

bool check(int mid)
{
    kopija = niz;
    int cnt = 0;
    int trd = niz[0].fi;
    for(int i=0; i<m; i++)
    {
        if(cnt >= mid)
        {
            cnt = 0;
            trd++;
        }
        if(kopija[i].fi > trd)
        {
            trd = kopija[i].fi;
            cnt = 0;
        }
        else
        {
            cnt++;
            if(trd - kopija[i].fi > d)return false;
        }
        kopija[i].fi = trd;
    }
    resenje = kopija;
    return true;
}


signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        cin >> n >> d >> m;
        niz.resize(m);
        for(int i=0; i<m; i++)cin >> niz[i].fi, niz[i].sc = i;
        sort(all(niz));
        int l = 1;
        int r = m;
        int rez = m;
        while(l<=r)
        {
            int mid = l + r>>1;
            if(check(mid))
            {
                r = mid-1;
                rez = mid;
            }
            else l = mid+1;
        }
        cout << rez << endl;
        sort(all(resenje));
        vector<vector<int>> mat(n+1);
        for(int i=0; i<resenje.size(); i++)
        {
            mat[resenje[i].fi].pb(resenje[i].sc);
        }
        for(int i=1; i<=n; i++)
        {
            if(!mat[i].size())
            {
                cout << 0 << endl;
                continue;
            }
            for(auto x: mat[i])cout << x+1 << " ";
            cout << 0 << endl;
        }
    }
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:64:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |             int mid = l + r>>1;
      |                       ~~^~~
jobs.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i=0; i<resenje.size(); i++)
      |                      ~^~~~~~~~~~~~~~~

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	4472 KB	Output is correct
2	Correct	39 ms	4176 KB	Output is correct
3	Correct	36 ms	4476 KB	Output is correct
4	Correct	36 ms	4168 KB	Output is correct
5	Correct	43 ms	4176 KB	Output is correct
6	Correct	35 ms	4168 KB	Output is correct
7	Correct	35 ms	4176 KB	Output is correct
8	Correct	34 ms	4432 KB	Output is correct
9	Correct	166 ms	6472 KB	Output is correct
10	Correct	170 ms	6472 KB	Output is correct
11	Correct	30 ms	4312 KB	Output is correct
12	Correct	58 ms	8156 KB	Output is correct
13	Correct	82 ms	11592 KB	Output is correct
14	Correct	129 ms	15688 KB	Output is correct
15	Correct	136 ms	17992 KB	Output is correct
16	Correct	177 ms	24392 KB	Output is correct
17	Correct	214 ms	30236 KB	Output is correct
18	Correct	240 ms	32072 KB	Output is correct
19	Runtime error	389 ms	34376 KB	Memory limit exceeded
20	Correct	210 ms	30280 KB	Output is correct