oj.uz

Submission #157703

# Submission time Handle Problem Language Result Execution time Memory
157703 2019-10-12T18:12:04 Z mrtsima22 Job Scheduling (CEOI12_jobs) C++17
55 / 100
 287 ms 13788 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;
	}
}
l+=2;
while(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 21 ms 1784 KB Output isn't correct
3 Incorrect 21 ms 1784 KB Output isn't correct
4 Incorrect 21 ms 1724 KB Output isn't correct
5 Incorrect 21 ms 1684 KB Output isn't correct
6 Incorrect 21 ms 1784 KB Output isn't correct
7 Incorrect 21 ms 1784 KB Output isn't correct
8 Incorrect 21 ms 1784 KB Output isn't correct
9 Correct 37 ms 1912 KB Output is correct
10 Correct 36 ms 1912 KB Output is correct
11 Correct 31 ms 1724 KB Output is correct
12 Correct 61 ms 3292 KB Output is correct
13 Correct 91 ms 4740 KB Output is correct
14 Correct 132 ms 6188 KB Output is correct
15 Incorrect 155 ms 7672 KB Output isn't correct
16 Correct 194 ms 9208 KB Output is correct
17 Correct 227 ms 10616 KB Output is correct
18 Correct 252 ms 12152 KB Output is correct
19 Correct 287 ms 13788 KB Output is correct
20 Correct 228 ms 10628 KB Output is correct