Submission #1109733

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109733	2024-11-07T12:45:30 Z	MrPavlito	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	525 ms	36920 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 = 2e5+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(MAXN);
        for(int i=0; i<resenje.size(); i++)
        {
            mat[resenje[i].fi].pb(resenje[i].sc);
        }
        for(int i=0; i<MAXN; i++)
        {
            if(!mat[i].size())
            {
                cout << 0 << endl;
                continue;
            }
            for(auto x: mat[i])cout << x << " ";
            cout << 0 << endl;
        }
    }
}

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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	288 ms	8772 KB	Expected EOLN
2	Incorrect	305 ms	8840 KB	Expected EOLN
3	Incorrect	286 ms	8776 KB	Expected EOLN
4	Incorrect	292 ms	8988 KB	Expected EOLN
5	Incorrect	299 ms	8896 KB	Expected EOLN
6	Incorrect	289 ms	8784 KB	Expected EOLN
7	Incorrect	294 ms	8776 KB	Expected EOLN
8	Incorrect	290 ms	8776 KB	Expected EOLN
9	Incorrect	307 ms	8896 KB	Expected EOLN
10	Incorrect	296 ms	9176 KB	Expected EOLN
11	Incorrect	294 ms	8776 KB	Expected EOLN
12	Incorrect	330 ms	12516 KB	Expected EOLN
13	Incorrect	359 ms	16456 KB	Expected EOLN
14	Incorrect	392 ms	20320 KB	Expected EOLN
15	Incorrect	416 ms	22668 KB	Expected EOLN
16	Incorrect	431 ms	26396 KB	Expected EOLN
17	Incorrect	470 ms	31784 KB	Expected EOLN
18	Runtime error	510 ms	33856 KB	Memory limit exceeded
19	Runtime error	525 ms	36920 KB	Memory limit exceeded
20	Incorrect	494 ms	31816 KB	Expected EOLN