oj.uz

Submission #898868

# Submission time Handle Problem Language Result Execution time Memory
898868 2024-01-05T08:19:21 Z 7again Job Scheduling (CEOI12_jobs) C++17
100 / 100
 333 ms 15780 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 2140 KB Output is correct
2 Correct 26 ms 2136 KB Output is correct
3 Correct 32 ms 2140 KB Output is correct
4 Correct 26 ms 2136 KB Output is correct
5 Correct 25 ms 2140 KB Output is correct
6 Correct 25 ms 2136 KB Output is correct
7 Correct 26 ms 2136 KB Output is correct
8 Correct 26 ms 2140 KB Output is correct
9 Correct 151 ms 2128 KB Output is correct
10 Correct 136 ms 2388 KB Output is correct
11 Correct 22 ms 2140 KB Output is correct
12 Correct 44 ms 3668 KB Output is correct
13 Correct 64 ms 5480 KB Output is correct
14 Correct 110 ms 7148 KB Output is correct
15 Correct 106 ms 8784 KB Output is correct
16 Correct 142 ms 10628 KB Output is correct
17 Correct 178 ms 12360 KB Output is correct
18 Correct 180 ms 13616 KB Output is correct
19 Correct 333 ms 15780 KB Output is correct
20 Correct 165 ms 12368 KB Output is correct