oj.uz

Submission #500413

# Submission time Handle Problem Language Result Execution time Memory
500413 2021-12-30T23:32:37 Z HediChehaidar Job Scheduling (CEOI12_jobs) C++17
100 / 100
 161 ms 13888 KB 
/*
ID: hedichehaidar
TASK: cowtour
LANG: C++11
*/
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = 998244353;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;


vi task[(int)1e5 + 10];
int need[(int)1e5 + 10];
int main(){
    //ifstream fin ("testing.txt");
    //ofstream fout ("output.txt");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n , d , m; cin>>n>>d>>m;
    for(int i = 0 ; i < m ; i++){
        int x; cin>>x; task[x].pb(i + 1);
    }
    int l = 1 , r = m , ans = m;
    while(l <= r){
        int mid = (l+r) / 2;
        bool ok  = true;
        int cur = 0 , all = 0;
        for(int i = 1 ; i <= n ; i++) need[i] = 0;
        for(int i = 1 ; i <= n ; i++){
            need[i] += need[i - 1];
            //if(mid == 1) cout << need[i] << " " << cur << "   ";
            need[i + d] += task[i].size();
            all += task[i].size();
            cur += min(all , mid);
            all -= min(all , mid);
            if(cur < need[i]){
                ok = false; break;
            }
        }
        //if(mid == 1) cout << "\n";
        if(ok){
            ans = mid; r = mid - 1;
        }
        else l = mid + 1;
    }
    queue<int> q;
    cout << ans << "\n";
    for(int i = 1 ; i <= n ; i++){
        for(auto c : task[i]) q.push(c);
        for(int j = 0 ; j < ans ; j++){
            if(q.empty()) break;
            cout << q.front() << " ";
            q.pop();
        }
        cout << 0 << "\n";
    }
    return 0;
}

/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO / HLD
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4132 KB Output is correct
2 Correct 15 ms 4084 KB Output is correct
3 Correct 15 ms 4060 KB Output is correct
4 Correct 15 ms 4104 KB Output is correct
5 Correct 15 ms 4144 KB Output is correct
6 Correct 15 ms 4144 KB Output is correct
7 Correct 15 ms 4044 KB Output is correct
8 Correct 19 ms 4044 KB Output is correct
9 Correct 26 ms 4476 KB Output is correct
10 Correct 23 ms 4428 KB Output is correct
11 Correct 16 ms 3788 KB Output is correct
12 Correct 30 ms 5000 KB Output is correct
13 Correct 45 ms 6792 KB Output is correct
14 Correct 70 ms 8132 KB Output is correct
15 Correct 71 ms 9036 KB Output is correct
16 Correct 108 ms 10756 KB Output is correct
17 Correct 118 ms 12644 KB Output is correct
18 Correct 161 ms 12628 KB Output is correct
19 Correct 137 ms 13888 KB Output is correct
20 Correct 133 ms 12612 KB Output is correct