oj.uz

답안 #152171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152171 2019-09-06T16:17:55 Z 12tqian Job Scheduling (CEOI12_jobs) C++14
100 / 100
 911 ms 29356 KB 
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
const double PI = 4 * atan(1);
 
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>
 
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
 
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
 
void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
const int MAX = 1e5 + 5;

vi dates[MAX];
vpi jobs;
int n, d, m;

int check(int use){
	vpi left;
	for(auto x: jobs) left.eb(x);
	reverse(all(left));
	int avail = use;
	f1r(i, 1, n+1) dates[i].clear();
	int cur = 1;
	while(sz(left)>0){
		while(avail>0){
			if(sz(left) == 0){
				return 1;
			}
			avail--;
			int element = left[sz(left) - 1].f;
			
			if(element>cur) break;
			dates[cur].eb(left[sz(left) - 1].s);
		//	cout << element + d << " " << cur << endl;
			if(element + d<cur) return 0;
			left.pop_back();
		}
		avail = use;
		cur++;
	}
	return 1;
	
}

int main(){
	fast_io();
	cin >> n >> d >> m;
	f0r(i, m){
		int t;
		cin >> t;
		jobs.eb(mp(t, i+1));
	}
	sort(all(jobs));
	int l = 1;
	int r = 1e6 + 5;
	while(abs(l-r)>1){
		int mid = (l + r)/2;
		if(check(mid)) r = mid;
		else l = mid+1;
	}
	if(l>r) swap(l, r);
	int val = -1;
	if(check(l)){
		//do nothing
		val = l;
	}
	else{
		val = r;
		assert(check(r));
	}
//	gen(val);
	cout << val << endl;
	f1r(i, 1, n+1){
		for(auto x: dates[i]){
			cout << x << " ";
		}	
		cout << 0 << endl;
	}
	
	return 0;
}

Compilation message

jobs.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
jobs.cpp: In function 'void io(std::__cxx11::string)':
jobs.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
jobs.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 6488 KB Output is correct
2 Correct 69 ms 6612 KB Output is correct
3 Correct 67 ms 6488 KB Output is correct
4 Correct 67 ms 6620 KB Output is correct
5 Correct 68 ms 6616 KB Output is correct
6 Correct 67 ms 6624 KB Output is correct
7 Correct 67 ms 6616 KB Output is correct
8 Correct 67 ms 6680 KB Output is correct
9 Correct 328 ms 5864 KB Output is correct
10 Correct 340 ms 5892 KB Output is correct
11 Correct 77 ms 5968 KB Output is correct
12 Correct 159 ms 8980 KB Output is correct
13 Correct 257 ms 13796 KB Output is correct
14 Correct 337 ms 18524 KB Output is correct
15 Correct 327 ms 17504 KB Output is correct
16 Correct 509 ms 23700 KB Output is correct
17 Correct 546 ms 27576 KB Output is correct
18 Correct 609 ms 27736 KB Output is correct
19 Correct 911 ms 29356 KB Output is correct
20 Correct 547 ms 27404 KB Output is correct