oj.uz

Submission #157702

# Submission time Handle Problem Language Result Execution time Memory
157702 2019-10-12T18:10:48 Z mrtsima22 Job Scheduling (CEOI12_jobs) C++17
55 / 100
 285 ms 13944 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[1000004];
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;
n=bin();
m=bin();
k=bin();
for(int i=1;i<=k;i++){
//	cin>>a[i].f;
	a[i].f=bin();
	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;
printf("%d\n",l);
int i=1,O=0;
while(i<=k){
	int L=l;
	while(L--&&i<=k){
//		cout<<a[i].s<<" ";
		printf("%d ",a[i].s);
		i++;
	}
//	cout<<0<<endl;
	printf("%d\n",0);
	O++;
}
O++;
while(O<=n){
//	cout<<0<<endl;
	printf("%d\n",0);
	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:97:13:
  int md=mid(l,r);
             ~~~     
jobs.cpp:97:9: note: in expansion of macro 'mid'
  int md=mid(l,r);
         ^~~

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1784 KB Output isn't correct
2 Incorrect 24 ms 1784 KB Output isn't correct
3 Incorrect 21 ms 1784 KB Output isn't correct
4 Incorrect 22 ms 1784 KB Output isn't correct
5 Incorrect 24 ms 1784 KB Output isn't correct
6 Incorrect 22 ms 1784 KB Output isn't correct
7 Incorrect 21 ms 1784 KB Output isn't correct
8 Incorrect 21 ms 1788 KB Output isn't correct
9 Correct 38 ms 2020 KB Output is correct
10 Correct 37 ms 1912 KB Output is correct
11 Correct 30 ms 1656 KB Output is correct
12 Correct 62 ms 3192 KB Output is correct
13 Correct 97 ms 4732 KB Output is correct
14 Correct 129 ms 6136 KB Output is correct
15 Incorrect 154 ms 7648 KB Output isn't correct
16 Correct 194 ms 9184 KB Output is correct
17 Correct 225 ms 10608 KB Output is correct
18 Correct 252 ms 12128 KB Output is correct
19 Correct 285 ms 13944 KB Output is correct
20 Correct 225 ms 10616 KB Output is correct