# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
78359 | 2018-10-04T05:36:27 Z | SamAnd | Job Scheduling (CEOI12_jobs) | C++17 | 280 ms | 33792 KB |
#include <bits/stdc++.h> using namespace std; #define m_p make_pair const int N=1000006; struct ban { int x,i; }; bool operator<(const ban& a,const ban& b) { if(a.x<b.x) return true; if(a.x>b.x) return false; return a.i<b.i; } int n,d,m; ban a[N]; vector<int> v[N]; void stgg(int x) { int o=1,xx=0; for(int i=0;i<m;++i) { while(a[i].x>o) { ++o; xx=0; } ++xx; v[o].push_back(a[i].i); if(xx==x) { ++o; xx=0; } } } bool stg(int x) { int o=1,xx=0; for(int i=0;i<m;++i) { while(a[i].x>o) { ++o; xx=0; } if(o>n) return false; if(a[i].x+d<o) return false; ++xx; if(xx==x) { ++o; xx=0; } } return true; } int byn() { int l=1,r=m; while((r-l)>3) { int mid=(l+r)/2; if(stg(mid)) r=mid; else l=mid; } for(int mid=l;mid<=r;++mid) if(stg(mid)) return mid; } int main() { //freopen("input.txt","r",stdin); scanf("%d%d%d",&n,&d,&m); for(int i=0;i<m;++i) { scanf("%d",&a[i].x); a[i].i=i+1; } sort(a,a+m); int ans=byn(); stgg(ans); cout<<ans<<endl; for(int i=1;i<=n;++i) { for(int j=0;j<v[i].size();++j) cout<<v[i][j]<<' '; cout<<0<<endl; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 25716 KB | Output is correct |
2 | Correct | 74 ms | 25728 KB | Output is correct |
3 | Correct | 65 ms | 25744 KB | Output is correct |
4 | Correct | 101 ms | 25748 KB | Output is correct |
5 | Correct | 66 ms | 25876 KB | Output is correct |
6 | Correct | 68 ms | 25972 KB | Output is correct |
7 | Correct | 66 ms | 25972 KB | Output is correct |
8 | Correct | 68 ms | 25972 KB | Output is correct |
9 | Correct | 222 ms | 26256 KB | Output is correct |
10 | Correct | 225 ms | 26280 KB | Output is correct |
11 | Correct | 68 ms | 26280 KB | Output is correct |
12 | Correct | 97 ms | 27948 KB | Output is correct |
13 | Correct | 138 ms | 30380 KB | Output is correct |
14 | Correct | 213 ms | 32536 KB | Output is correct |
15 | Runtime error | 230 ms | 33324 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
16 | Runtime error | 280 ms | 33792 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
17 | Runtime error | 257 ms | 33792 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
18 | Runtime error | 264 ms | 33792 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
19 | Runtime error | 278 ms | 33792 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
20 | Runtime error | 251 ms | 33792 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |