답안 #759110

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759110 2023-06-15T18:55:28 Z Charizard2021 Job Scheduling (CEOI12_jobs) C++17
0 / 100
232 ms 19908 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++){
        for(int j = 0; j < ans[i].size(); j++){
            cout << ans[i][j] + 1 << " ";
        }
        cout << "0\n";
    }
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:142:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for(int j = 0; j < ans[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 3020 KB Output isn't correct
2 Incorrect 24 ms 3020 KB Output isn't correct
3 Incorrect 23 ms 3116 KB Output isn't correct
4 Incorrect 32 ms 3052 KB Output isn't correct
5 Incorrect 33 ms 3012 KB Output isn't correct
6 Incorrect 23 ms 3060 KB Output isn't correct
7 Incorrect 24 ms 3044 KB Output isn't correct
8 Incorrect 24 ms 3052 KB Output isn't correct
9 Incorrect 33 ms 6824 KB Output isn't correct
10 Incorrect 26 ms 6908 KB Output isn't correct
11 Incorrect 23 ms 2004 KB Output isn't correct
12 Incorrect 45 ms 3520 KB Output isn't correct
13 Incorrect 66 ms 6536 KB Output isn't correct
14 Incorrect 108 ms 8380 KB Output isn't correct
15 Incorrect 110 ms 9084 KB Output isn't correct
16 Incorrect 159 ms 11976 KB Output isn't correct
17 Incorrect 188 ms 14796 KB Output isn't correct
18 Incorrect 175 ms 14696 KB Output isn't correct
19 Incorrect 207 ms 19908 KB Output isn't correct
20 Incorrect 232 ms 14808 KB Output isn't correct