oj.uz

Submission #157696

# Submission time Handle Problem Language Result Execution time Memory
157696 2019-10-12T18:06:46 Z mrtsima22 Job Scheduling (CEOI12_jobs) C++17
15 / 100
 1000 ms 2040 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;
int i=1,O=0;
while(i<=k){
	int L=l;
	while(L--&&i<=k){
		cout<<a[i].s<<" ";
		i++;
	}
	cout<<0<<endl;
	O++;
}
O++;
while(O<=n){
	cout<<0<<endl;
	O++;
}
}
/*

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


*/

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);
         ^~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 1784 KB Output isn't correct
2 Incorrect 49 ms 1772 KB Output isn't correct
3 Incorrect 49 ms 1756 KB Output isn't correct
4 Incorrect 49 ms 1656 KB Output isn't correct
5 Incorrect 49 ms 1784 KB Output isn't correct
6 Incorrect 49 ms 1784 KB Output isn't correct
7 Incorrect 49 ms 1656 KB Output isn't correct
8 Incorrect 50 ms 1656 KB Output isn't correct
9 Correct 291 ms 1912 KB Output is correct
10 Correct 294 ms 2040 KB Output is correct
11 Correct 35 ms 1784 KB Output is correct
12 Execution timed out 1070 ms 1144 KB Time limit exceeded
13 Execution timed out 1063 ms 1116 KB Time limit exceeded
14 Execution timed out 1071 ms 1116 KB Time limit exceeded
15 Execution timed out 1054 ms 1144 KB Time limit exceeded
16 Execution timed out 1071 ms 1144 KB Time limit exceeded
17 Execution timed out 1067 ms 1100 KB Time limit exceeded
18 Execution timed out 1054 ms 1144 KB Time limit exceeded
19 Execution timed out 1059 ms 1116 KB Time limit exceeded
20 Execution timed out 1025 ms 1144 KB Time limit exceeded