Submission #157692

# Submission time Handle Problem Language Result Execution time Memory
157692 2019-10-12T18:01:16 Z mrtsima22 Job Scheduling (CEOI12_jobs) C++17
0 / 100
1000 ms 1272 KB
#pragma GCC optimize "-O3"
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define NumberOfOnes __builtin_popcount
#define LSOne(S) (S & (-S))
#define ll long long
#define two pair<int,int>
#define twoll pair<ll,ll>
#define four pair<two,two>
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define y1 y1922
#define INF 1000000000000000000
#define P 1000000007
#define lmax 1000000000
#define nn 1000003
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define vi vector<int>
#define vll vector<ll>
#define vtwo vector<two>
#define ALL(container) (container).begin(), (container).end()
#define sz(container) (int)(container.size())
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mid(a,b) (a+b>>1)
#define minN 0
#define maxN 10000000
#define na(x) ((x)<P?(x):(x)-P)
#define ab(a) (-(a)<(a)?(a):-(a))
#define FAST std::ios::sync_with_stdio(false)
#define xRand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rnd rng
#define IT iterator
typedef
tree<
  int,// aq pair<int,int> shegidzlia
  null_type,
  less/*_equal*/<int>,// aqac
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
// '_equal' mashin ginda roca multiset gchirdeba
template<class key, class value,class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
ordered_map<int, int> my_map;
inline int rin(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
inline int bin(){
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
int n,m,k;
two a[100004];
bool che(int g){
	int u=1,o=0;
	while(u<k){
		int d=g;
		o++;
		while(d--&&u<k){
			if(a[u].f+m<o) return 0;
			u++;
		}
		if(u>k) return 1;
	}
	return 1;
}
int main(){FAST;xRand;
cin>>n>>m>>k;
for(int i=1;i<=k;i++){
	cin>>a[i].f;
	a[i].s=i;
}
sort(a+1,a+1+k);
int l=1,r=k;
while(l<r){
	int md=mid(l,r);
	if(che(md)){
		r=md;
	}else{
		l=md+1;
	}
}
if(che(l-1)) l--;
cout<<l<<endl;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/

Compilation message

jobs.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
jobs.cpp: In function 'int main()':
jobs.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid(a,b) (a+b>>1)
jobs.cpp:93:13:
  int md=mid(l,r);
             ~~~     
jobs.cpp:93:9: note: in expansion of macro 'mid'
  int md=mid(l,r);
         ^~~
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1144 KB Output isn't correct
2 Incorrect 15 ms 1144 KB Output isn't correct
3 Incorrect 15 ms 1144 KB Output isn't correct
4 Incorrect 15 ms 1148 KB Output isn't correct
5 Incorrect 15 ms 1144 KB Output isn't correct
6 Incorrect 15 ms 1144 KB Output isn't correct
7 Incorrect 15 ms 1272 KB Output isn't correct
8 Incorrect 16 ms 1144 KB Output isn't correct
9 Incorrect 24 ms 1144 KB Unexpected end of file - int32 expected
10 Incorrect 24 ms 1144 KB Unexpected end of file - int32 expected
11 Incorrect 25 ms 1144 KB Unexpected end of file - int32 expected
12 Execution timed out 1084 ms 1144 KB Time limit exceeded
13 Execution timed out 1087 ms 1144 KB Time limit exceeded
14 Execution timed out 1059 ms 1144 KB Time limit exceeded
15 Execution timed out 1083 ms 1144 KB Time limit exceeded
16 Execution timed out 1077 ms 1144 KB Time limit exceeded
17 Execution timed out 1079 ms 1144 KB Time limit exceeded
18 Execution timed out 1083 ms 1144 KB Time limit exceeded
19 Execution timed out 1080 ms 1144 KB Time limit exceeded
20 Execution timed out 1061 ms 1144 KB Time limit exceeded