Submission #636298

#TimeUsernameProblemLanguageResultExecution timeMemory
636298jcheng25Job Scheduling (CEOI12_jobs)C++17
0 / 100
387 ms21180 KiB
#include <bits/stdc++.h>
 
 const std::string filename = "sabotage";
using namespace std;
#define c() {cout << "CHECKPOINT\n";}
#define b(I) {cout << "BREAKPOINT. POINT: " << I << "\n";}
#define cb(G, I) {if(G) cout << "CONDITIONAL BREAKPOINT. FUFILLS " << #G << ". POINT: " << I << "\n";}
#define see(ARRAY) {cout<<"Watching Values Of "<<#ARRAY<<" { ";for(auto& e : ARRAY) {cout << e << " ";}cout<<" }\n";}
#define see2d(ARRAY) {cout<<"Watching Values Of "<<#ARRAY<<"\n {\n";for(auto&e:ARRAY){cout<<"{ ";for(auto&a:e){cout<<a<<" ";}cout<<"}\n";}cout<<" }\n";}
#define see2dE(ARRAY,A) {cout<<"Watching Values Of "<<#ARRAY<<" with bounds " << A << "\n {\n";for(int i=0; i < A; i++){for(int j = 0; j < A; j++)cout<<ARRAY[i][j]<<" ";cout<<"\n";}cout<<" }\n";}
#define see2dF(ARRAY,A) {cout<<"Watching Values Of "<<#ARRAY<<" with semibounds " << A << "\n {\n";for(int i=0; i < A; i++){for(int j = 0; j < (int)(ARRAY[i].size()); j++)cout<<ARRAY[i][j]<<" ";cout<<"\n";}cout<<" }\n";}
#define seePair(PAIR) {cout<<"Watching Value Of "<<#PAIR<<" { "<<PAIR.first<<", "<<PAIR.second<<" }\n";};
#define mset multiset
#define inv_priority_queue priority_queue<ll, vector<ll>, greater<ll>>
#define ll long long
#define ld long double
#define pi pair<int, int>
#define pd pair<double, double>
#define pl pair<long long, long long>
#define szv(x) ((int)x.size())
#define sza(x) (int)(sizeof(x))
#define vall(a) (a).begin(), (a).end()
#define aall(a) a, a+(int)(sizeof(a))
#define mkp make_pair
#define fr first
#define sc second
#define bk back
#define pb push_back
#define ct cout << 
 
const int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
const int MAX_N = 1e5 + 5;
const int MAX_DN = 105;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;

vector<pi> A;

pair<bool, vector<vector<int>>> works(ll test, int D) {

	vector<vector<int>> schedule;

	int i = 0, count = 1, next = test;
	while(i < szv(A)) {

		schedule.pb({});

		if(!(count - A[i].fr <= D)) return mkp(false, schedule);


		for( ; i < min(next, szv(A)); i++) {

			if(count - A[i].fr < 0) break;

			schedule.back().pb(A[i].sc);
		}

		schedule.back().pb(0);

		count++;
		next += test;
	}

	return mkp(true, schedule);
}


void solve(int testcase) {

	int N, D, M;
	cin >> N >> D >> M;

	for(int i = 0; i < M; i++) {
		int a;
		cin >> a;

		A.pb({a, i+1});
	}

	sort(vall(A));

	
	ll l = 1, h = M;
	while(l < h) {
		ll mid = (l + h) / 2;

		if(works(mid, D).fr) {
			h = mid;
		} else {
			l = mid+1;
		}
	}

	vector<vector<int>> ans = works(l, D).sc;

	cout << l << "\n";
	for(auto& e : ans) {
		for(auto& c : e) {
			cout << c << " ";
		}
		cout << "\n";
	}
}



					

void setIO() {  // name is nonempty for USACO file I/O
	string name = filename;
	ios_base::sync_with_stdio(0); cin.tie(0);  // see Fast Input & Output
	cin.tie(0)->sync_with_stdio(0);
	if (!(name == "*")) {
		freopen((name+".in").c_str(), "r", stdin);  // see Input & Output
		freopen((name+".out").c_str(), "w", stdout);
	}
}
 
int main() {
    //ios_base::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
	//setIO();	
 
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t << ": ";
        solve(t);
    }
}

Compilation message (stderr)

jobs.cpp: In function 'void setIO()':
jobs.cpp:115:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   freopen((name+".in").c_str(), "r", stdin);  // see Input & Output
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:116:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...