Submission #481513

#TimeUsernameProblemLanguageResultExecution timeMemory
481513RahkinJob Scheduling (CEOI12_jobs)C++14
55 / 100
1097 ms34080 KiB
#include "bits/stdc++.h"
using namespace std;
/*------------------------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*------------------------------------------------------------------*/
#define int               long long
#define nl                "\n"
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define rall(x)           (x).rbegin(),(x).rend()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define fix(prec)         {cout << setprecision(prec) << fixed;}
#define lcm(a, b)         ((a) * (b)) / __gcd(a, b)
#define rev               greater<int>()
#define Max(x,y,z)        max(x,max(y,z))
#define Min(x,y,z)        min(x,min(y,z))
#define imin              INT_MIN
#define imax              INT_MAX
#define Yes               cout<<"Yes\n"
#define No                cout<<"No\n"
#define YES               cout<<"YES\n"
#define NO                cout<<"NO\n"
#define yes               cout<<"yes\n"
#define no                cout<<"no\n"
#define show(A) for (auto i: A) cout << i << " "; cout << '\n';
#define endl "\n"

using ld = long double;
using vi = vector < int > ;
using mi = map < int, int > ;
using pi = pair < int, int > ;

const double Pi = acos(-1.0);
const int inf = 1e18 + 1;
const int M = 1e9 + 7;
const int MM = 998244353;

const int N1 = 1e5 + 5;
const int N2 = 1e6 + 5;

int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, -1, 1, 1, -1};

template<typename T, typename T1>T amax(T &a, T1 b) {if (b > a)a = b; return a;}
template<typename T, typename T1>T amin(T &a, T1 b) {if (b < a)a = b; return a;}
/*----------------------------------------------------------*/
void setIO(string s)
{
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
void local()
{
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}
/*--------------------------------------------------------*/

int n,d,m;
bool ok(int x,vector<pair<int,int>> &v)
{
	int day=1;
	int c=x;
	int del=0;
	for(int i=0;i<(int)v.size();i++)
	{
		if(c==0)
		{
			day++;
			c=x;
			if(day>=v[i].fr)
			{
				c--;
				del=max(del,day-v[i].fr);
			}
			else
			{
				day+=v[i].fr-day;
				c--;
			}
		}
		else 
		{
			if(day>=v[i].fr)
			{
				c--;
				del=max(del,day-v[i].fr);
			}
			else
			{
				day+=v[i].fr-day;
				c--;
			}
	  }
	  //debug(i,del);
	}
	//debug(x,del,day);
	return del<=d;
}
signed main()
{

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

	cin>>n>>d>>m;
	vector<pair<int,int> > v;
	for(int i=0;i<m;i++)
	{
		int x;
		cin>>x;
		v.pb({x,i+1});
	}
	sort(all(v));
	debug(v);
	int l=1,r=m;
	while(l<r)
	{
		int mid=l+(r-l)/2;
		if(ok(mid,v))
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<l<<nl;
	int day=1;
	int x=l;
	int b=0;
	for(int i=0;i<(int)v.size();)
	{
		int f=0,j;
		for(j=i;j<i+x && j<(int)v.size();j++)
		{
			if(v[j].fr<=day)
			{
				cout<<v[j].sc<<" ";
			}
			else
			{
				cout<<0<<nl;
				b++;
				day++;
				f=1;
				break;
			}
		}
		if(f==0)
		{
			day++;
			cout<<0<<nl;
			b++;
		}
		i=j;
	}
	for(int i=1;i<=n-b;i++)
	cout<<0<<nl;


  return 0;

}

Compilation message (stderr)

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:83:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:84:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void local()':
jobs.cpp:89:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:90:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...