| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 481524 | Rahkin | Job Scheduling (CEOI12_jobs) | C++14 | 239 ms | 20884 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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));
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 c=l;
int x=l;
int b=0;
int del=0;
for(int i=0;i<(int)v.size();i++)
{
if(c==0)
{
cout<<0<<nl;
b++;
day++;
c=x;
if(day>=v[i].fr)
{
c--;
del=max(del,day-v[i].fr);
cout<<v[i].sc<<" ";
}
else
{
cout<<0<<nl;
b++;
day+=v[i].fr-day;
c--;
}
}
else
{
if(day>=v[i].fr)
{
c--;
del=max(del,day-v[i].fr);
cout<<v[i].sc<<" ";
}
else
{
cout<<0<<nl;
day+=v[i].fr-day;
c--;
b++;
}
}
}
for(int i=1;i<=n-b;i++)
{
cout<<0<<nl;
}
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||