oj.uz

Submission #1109734

# Submission time Handle Problem Language Result Execution time Memory
1109734 2024-11-07T12:46:51 Z MrPavlito Job Scheduling (CEOI12_jobs) C++17
0 / 100
 383 ms 36676 KB 
#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=1; i<=n; 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 34 ms 8528 KB Expected EOLN
2 Incorrect 33 ms 8528 KB Expected EOLN
3 Incorrect 34 ms 8528 KB Expected EOLN
4 Incorrect 33 ms 8528 KB Expected EOLN
5 Incorrect 33 ms 8528 KB Expected EOLN
6 Incorrect 33 ms 8528 KB Expected EOLN
7 Incorrect 33 ms 8528 KB Expected EOLN
8 Incorrect 35 ms 8520 KB Expected EOLN
9 Incorrect 164 ms 8776 KB Expected EOLN
10 Incorrect 164 ms 8776 KB Expected EOLN
11 Incorrect 28 ms 8520 KB Expected EOLN
12 Incorrect 57 ms 12104 KB Expected EOLN
13 Incorrect 78 ms 16200 KB Expected EOLN
14 Incorrect 122 ms 19784 KB Expected EOLN
15 Incorrect 148 ms 22096 KB Expected EOLN
16 Incorrect 179 ms 25888 KB Expected EOLN
17 Incorrect 222 ms 31280 KB Expected EOLN
18 Runtime error 247 ms 33352 KB Memory limit exceeded
19 Runtime error 383 ms 36676 KB Memory limit exceeded
20 Incorrect 199 ms 31560 KB Expected EOLN