oj.uz

Submission #759107

# Submission time Handle Problem Language Result Execution time Memory
759107 2023-06-15T18:53:13 Z Charizard2021 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 238 ms 23284 KB 
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);; cin.tie(NULL)
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& x) {return in >> x.first >> x.second;}

template<typename T1, typename T2> ostream& operator<<(ostream& out, const pair<T1, T2>& x) {return out << x.first << ' ' << x.second;}
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};
template<typename T> ostream& operator<<(ostream& out, vector<vector<T> >& a) {for(auto &x : a) out << x << '\n'; return out;};
template<typename T1, typename T2> ostream& operator<<(ostream& out, vector<pair<T1, T2> >& a) {for(auto &x : a) out << x << '\n'; return out;};
void selfMax(int& a, int b){
    a = max(a, b);
}
void selfMin(int& a, int b){
    a = min(a, b);
}
/*

Use DSU dsu(N);

*/
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }

	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	bool same_set(int a, int b) { return get(a) == get(b); }

	int size(int x) { return -e[get(x)]; }

	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x;
		return true;
	}
};
/*

Run with Bit<int> BIT

*/
template <class T> class BIT {
    private:
        int size;
        vector<T> bit;
        vector<T> arr;
    public:
        BIT(int size) : size(size), bit(size + 1), arr(size) {}
        void set(int ind, int val) { add(ind, val - arr[ind]); }
        void add(int ind, int val) {
            arr[ind] += val;
            ind++;
            for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
        }
        T pref_sum(int ind) {
            ind++;
            T total = 0;
            for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
            return total;
        }
};
/*

Change Comb for specific Seg tree probs, but run with Seg<int> Seg;

*/
template<class T> struct Seg {
	const T ID = 1e18; T comb(T a, T b) { return min(a,b); }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) {
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};
bool works(int x, vector<vector<int> >& adj, int n, int d, int m){
    queue<int> q;
    for(int i = 0; i < n; i++){
        for(int v : adj[i]){
            q.push(i);
        }
        int cur = x;
        while(cur != 0 && !q.empty()){
            int u = q.front();
            q.pop();
            if(i - u > d){
                return false;
            }
            cur--;
        }
    }
    return true;
}

int main(){
    int n, d, m;
    cin >> n >> d >> m;
    vector<vector<int> > adj(n);
    for(int i = 0; i < m; i++){
        int x;
        cin >> x;
        adj[x].push_back(i);
    }
    int low = 1;
    int high = m;
    while(low < high){
        int mid = (low + high)/2;
        if(works(mid, adj, n, d, m)){
            high = mid;
        }
        else{
            low = mid + 1;
        }
    }
    cout << low << "\n";
    queue<pair<int, int> > q;
    vector<vector<int> > ans(n);
    for(int i = 0; i < n; i++){
        for(int v : adj[i]){
            q.push(make_pair(i, v));
        }
        int cur = low;
        while(cur != 0 && !q.empty()){
            pair<int, int> u = q.front();
            q.pop();
            ans[i].push_back(u.second);
            cur--;
        }
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << " ";
        cout << "0\n";
    }
}

Compilation message

jobs.cpp: In function 'bool works(int, std::vector<std::vector<int> >&, int, int, int)':
jobs.cpp:90:17: warning: unused variable 'v' [-Wunused-variable]
   90 |         for(int v : adj[i]){
      |                 ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 3268 KB Expected EOLN
2 Incorrect 33 ms 3324 KB Expected EOLN
3 Incorrect 32 ms 3336 KB Expected EOLN
4 Incorrect 29 ms 3300 KB Expected EOLN
5 Incorrect 27 ms 3304 KB Expected EOLN
6 Incorrect 26 ms 3260 KB Expected EOLN
7 Incorrect 25 ms 3240 KB Expected EOLN
8 Incorrect 24 ms 3312 KB Expected EOLN
9 Incorrect 32 ms 7200 KB Expected EOLN
10 Incorrect 32 ms 7296 KB Expected EOLN
11 Incorrect 26 ms 2384 KB Expected EOLN
12 Incorrect 52 ms 4504 KB Expected EOLN
13 Incorrect 77 ms 7624 KB Expected EOLN
14 Incorrect 120 ms 10828 KB Expected EOLN
15 Incorrect 125 ms 10252 KB Expected EOLN
16 Incorrect 191 ms 13912 KB Expected EOLN
17 Incorrect 209 ms 18840 KB Expected EOLN
18 Incorrect 210 ms 17776 KB Expected EOLN
19 Incorrect 238 ms 23284 KB Expected EOLN
20 Incorrect 218 ms 18892 KB Expected EOLN