oj.uz

Submission #818373

# Submission time Handle Problem Language Result Execution time Memory
818373 2023-08-10T04:32:38 Z trMatherz Job Scheduling (CEOI12_jobs) C++17
55 / 100
 379 ms 17928 KB 


      #include <iostream>

/*
#include <fstream>
std::ifstream cin ("shuffle.in");
std::ofstream cout ("shuffle.out");
*/

using namespace std;

#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <cstdio>
#include <iomanip>
#include <list>
#include <numeric>
#include <cmath>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()



#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define vvl vector<vl>
#define vpi vector<pair<int,int>>
#define vb vector<bool>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>

#define FR(x, a, b) for(int x = a; x < b; x++)
#define F(x, b) FR(x, 0, b)


#define f first
#define s second
#define ll long long

using namespace std;

/*
 8 2 12
 1 2 4 2 1 3 5 6 2 3 6 4
 */

int main(){
    int n, k, m; cin >> n >> k >> m;
    vi a(n); vpi p(m);
    F(i, m){cin >> p[i].f; p[i].f--; a[p[i].f]++; p[i].s = i + 1;}
    sort(all(p));
    auto check = [&](int x){
        int d = 0, dead = 0;
        while(d < n){
            int dl = x;
           
            while(dl > 0 && d < n){
                while(a[d] == 0 && d < n){d++;}
                int amt = min(a[d], dl);
                a[d] -= amt;
                dl -= amt;
            }
            while(a[d] == 0 && d < n){d++;}
            dead++;
            if(dead - d > k){ return false;}
        }
       
        return true;
    };
    
    int l = 1, r = 1e6;
    
    
    while(l < r){
        int mi = (r + l)/2;
        auto t = a;
        
        if(check(mi)){
            r = mi;
        } else {
            l = mi + 1;
        }
        a = t;
    }
   
    cout << l << endl;
    int po = 0;
    F(i, n){
        int c = l;
        while(c > 0 && po < m){
            cout << p[po].s << " ";
            c--;
            po++;
        }
        
        
        
        cout << 0 << endl;
    }
    
    return 0;
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 2016 KB Output isn't correct
2 Incorrect 38 ms 2060 KB Output isn't correct
3 Incorrect 34 ms 2068 KB Output isn't correct
4 Incorrect 32 ms 2060 KB Output isn't correct
5 Incorrect 32 ms 1968 KB Output isn't correct
6 Incorrect 32 ms 2060 KB Output isn't correct
7 Incorrect 39 ms 2172 KB Output isn't correct
8 Incorrect 32 ms 1952 KB Output isn't correct
9 Correct 126 ms 2864 KB Output is correct
10 Correct 129 ms 2848 KB Output is correct
11 Correct 31 ms 1996 KB Output is correct
12 Correct 61 ms 3832 KB Output is correct
13 Correct 92 ms 5700 KB Output is correct
14 Correct 144 ms 8060 KB Output is correct
15 Incorrect 154 ms 9452 KB Output isn't correct
16 Correct 224 ms 12048 KB Output is correct
17 Correct 251 ms 13900 KB Output is correct
18 Correct 257 ms 15160 KB Output is correct
19 Correct 379 ms 17928 KB Output is correct
20 Correct 272 ms 14012 KB Output is correct