oj.uz

Submission #152170

# Submission time Handle Problem Language Result Execution time Memory
152170 2019-09-06T16:16:45 Z 12tqian Job Scheduling (CEOI12_jobs) C++14
55 / 100
 903 ms 29576 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;
			dates[cur].eb(left[sz(left) - 1].s);
			if(element>cur) break;
		//	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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 68 ms 6744 KB Partially correct
2 Partially correct 69 ms 6752 KB Partially correct
3 Partially correct 67 ms 6868 KB Partially correct
4 Partially correct 67 ms 6748 KB Partially correct
5 Partially correct 67 ms 6880 KB Partially correct
6 Partially correct 68 ms 6876 KB Partially correct
7 Partially correct 68 ms 6752 KB Partially correct
8 Partially correct 68 ms 6756 KB Partially correct
9 Correct 331 ms 6088 KB Output is correct
10 Correct 331 ms 6124 KB Output is correct
11 Partially correct 70 ms 6080 KB Partially correct
12 Correct 140 ms 9236 KB Output is correct
13 Partially correct 236 ms 13892 KB Partially correct
14 Correct 312 ms 16124 KB Output is correct
15 Partially correct 325 ms 17956 KB Partially correct
16 Partially correct 526 ms 24356 KB Partially correct
17 Partially correct 542 ms 27908 KB Partially correct
18 Correct 615 ms 27944 KB Output is correct
19 Partially correct 903 ms 29576 KB Partially correct
20 Partially correct 546 ms 27736 KB Partially correct