oj.uz

Submission #898844

# Submission time Handle Problem Language Result Execution time Memory
898844 2024-01-05T07:52:35 Z hadi7 Job Scheduling (CEOI12_jobs) C++17
90 / 100
 310 ms 13908 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 ; j++)
        {
            while(p[u].f > i)
                i++ ;
 
            if(i > n || i - p[u].f > k)
                return 0 ;
 
            u++ ;
 
            if(u == m)
                return 1 ;
        }
    }
 
    return 0 ;
}
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++)
        {
            cout << p[u].s << " " ;
            u++ ;
        }
        cout << 0 << endl ;
    }
}

Compilation message

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

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1624 KB Output is correct
2 Correct 26 ms 1628 KB Output is correct
3 Correct 26 ms 1624 KB Output is correct
4 Correct 25 ms 1624 KB Output is correct
5 Correct 26 ms 1852 KB Output is correct
6 Correct 25 ms 1628 KB Output is correct
7 Correct 26 ms 1628 KB Output is correct
8 Correct 25 ms 1624 KB Output is correct
9 Correct 129 ms 1896 KB Output is correct
10 Correct 128 ms 1876 KB Output is correct
11 Correct 22 ms 1628 KB Output is correct
12 Correct 45 ms 3156 KB Output is correct
13 Correct 66 ms 4688 KB Output is correct
14 Correct 103 ms 6228 KB Output is correct
15 Incorrect 108 ms 7644 KB Output isn't correct
16 Correct 144 ms 9240 KB Output is correct
17 Correct 173 ms 10552 KB Output is correct
18 Correct 187 ms 12088 KB Output is correct
19 Incorrect 310 ms 13908 KB Output isn't correct
20 Correct 168 ms 10616 KB Output is correct