oj.uz

Submission #898840

# Submission time Handle Problem Language Result Execution time Memory
898840 2024-01-05T07:45:45 Z hadi7 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 310 ms 13892 KB 
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(0); cin.tie(0)
#define f first
#define s second
using namespace std ;

const int N = 2e6 ;
int n , k , m ;
vector <pair <int , int>> p ;

bool slv(int x)
{
    int u = 0 ;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 0 ; j < x && u < m && p[u].f <= i ; j++)
            if(i - p[u++].f > k)
                return 0 ;


    return (u == m) ;
}
main()
{
    FAST ;
    cin >> n >> k >> m ;
    p.resize(m) ;

    for(int i = 0 ; i < m ; i++)
    {
        cin >> p[i].f ;
        p[i].s = i + 1 ;
    }

    sort(p.begin() , p.end()) ;

    int l = 0 , r = N ;
    while(l + 1 < r)
    {
        int h = l + (r - l) / 2 ;
        if(slv(h))
            r = h ;
        else
            l = h ;
    }

    cout << r << endl ;

    int u = 0 ;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j < r && u < m && p[u].f <= i ; j++ , u++)
            cout << p[u].s << " " ;

        cout << 0 << endl ;
    }
}

Compilation message

jobs.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main()
      | ^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1624 KB Output is correct
2 Correct 25 ms 1880 KB Output is correct
3 Correct 26 ms 1628 KB Output is correct
4 Correct 25 ms 1732 KB Output is correct
5 Correct 25 ms 1864 KB Output is correct
6 Correct 25 ms 1624 KB Output is correct
7 Correct 25 ms 1628 KB Output is correct
8 Correct 25 ms 1628 KB Output is correct
9 Correct 131 ms 1860 KB Output is correct
10 Correct 128 ms 1856 KB Output is correct
11 Correct 22 ms 1624 KB Output is correct
12 Correct 43 ms 3564 KB Output is correct
13 Correct 63 ms 4692 KB Output is correct
14 Correct 99 ms 6224 KB Output is correct
15 Correct 105 ms 7688 KB Output is correct
16 Correct 141 ms 9044 KB Output is correct
17 Correct 165 ms 10556 KB Output is correct
18 Correct 179 ms 12116 KB Output is correct
19 Correct 310 ms 13892 KB Output is correct
20 Correct 165 ms 10548 KB Output is correct