oj.uz

Submission #759108

# Submission time Handle Problem Language Result Execution time Memory
759108 2023-06-15T18:53:31 Z Charizard2021 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 227 ms 20076 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(v);
        }
        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";
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 3012 KB Output isn't correct
2 Incorrect 24 ms 3016 KB Output isn't correct
3 Incorrect 24 ms 3148 KB Output isn't correct
4 Incorrect 25 ms 3020 KB Output isn't correct
5 Incorrect 26 ms 3028 KB Output isn't correct
6 Incorrect 25 ms 3008 KB Output isn't correct
7 Incorrect 26 ms 3020 KB Output isn't correct
8 Incorrect 23 ms 3120 KB Output isn't correct
9 Incorrect 28 ms 6904 KB Output isn't correct
10 Incorrect 28 ms 6944 KB Output isn't correct
11 Incorrect 24 ms 1912 KB Output isn't correct
12 Incorrect 59 ms 3532 KB Output isn't correct
13 Incorrect 72 ms 6456 KB Output isn't correct
14 Incorrect 115 ms 8424 KB Output isn't correct
15 Incorrect 115 ms 9036 KB Output isn't correct
16 Incorrect 169 ms 11816 KB Output isn't correct
17 Incorrect 196 ms 14880 KB Output isn't correct
18 Incorrect 184 ms 14700 KB Output isn't correct
19 Incorrect 227 ms 20076 KB Output isn't correct
20 Incorrect 199 ms 14824 KB Output isn't correct