oj.uz

답안 #759118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759118 2023-06-15T19:02:22 Z Charizard2021 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 271 ms 19944 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;
        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++){
        for(int j = 0; j < ans[i].size(); j++){
            cout << ans[i][j] + 1 << " ";
        }
        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]){
      |                 ^
jobs.cpp: In function 'int main()':
jobs.cpp:143:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         for(int j = 0; j < ans[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 3020 KB Output is correct
2 Correct 32 ms 3020 KB Output is correct
3 Correct 24 ms 2984 KB Output is correct
4 Correct 24 ms 3032 KB Output is correct
5 Correct 24 ms 2980 KB Output is correct
6 Correct 24 ms 3012 KB Output is correct
7 Correct 24 ms 3012 KB Output is correct
8 Correct 24 ms 3020 KB Output is correct
9 Correct 30 ms 6944 KB Output is correct
10 Correct 31 ms 6884 KB Output is correct
11 Correct 27 ms 2004 KB Output is correct
12 Correct 74 ms 3656 KB Output is correct
13 Correct 84 ms 6496 KB Output is correct
14 Correct 130 ms 8872 KB Output is correct
15 Correct 158 ms 8544 KB Output is correct
16 Correct 225 ms 11112 KB Output is correct
17 Correct 250 ms 15748 KB Output is correct
18 Correct 213 ms 14744 KB Output is correct
19 Correct 271 ms 19944 KB Output is correct
20 Correct 231 ms 15720 KB Output is correct