Submission #36686

#TimeUsernameProblemLanguageResultExecution timeMemory
36686RockyBJob Scheduling (CEOI12_jobs)C++11
100 / 100
749 ms22592 KiB
/// In The Name Of God #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx") #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define pp pop_back #define mp make_pair #define sz(x) (int)x.size() #define sqr(x) ((x) * 1ll * (x)) #define all(x) x.begin(), x.end() #define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define nl '\n' #define ioi exit(0); typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = (int)1e6 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7; const ll linf = (ll)1e18 + 7; const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; using namespace std; int n, d, m; pair <int, int> a[N]; int cnt[(int)1e5 + 7]; bool check(int total) { memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= m; i++) { bool ok = 0; for (int j = a[i].f; j <= a[i].f + d; j++) { if (cnt[j] < total) { cnt[j]++; ok = 1; break; } } if (!ok) return 0; } return 1; } int main() { #ifdef IOI2018 freopen ("in.txt", "r", stdin); #endif scanf ("%d%d%d", &n, &d, &m); for (int i = 1; i <= m; i++) { scanf ("%d", &a[i].f); a[i].s = i; } sort (a + 1, a + 1 + m); int l = 1, r = m, res = m; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) res = mid, r = mid - 1; else l = mid + 1; } { memset(cnt, 0, sizeof(cnt)); vector < pair <int, int> > ans; for (int i = 1; i <= m; i++) { for (int j = a[i].f; j <= a[i].f + d; j++) { if (cnt[j] < res) { cnt[j]++; ans.pb({j, a[i].s}); break; } } } printf ("%d\n", res); sort(all(ans)); int ptr = 0; for (int i = 1; i <= n; i++) { while (ptr < sz(ans) && ans[ptr].f < i) ptr++; while (ptr < sz(ans) && ans[ptr].f == i) { printf ("%d ", ans[ptr++].s); } printf ("0\n"); } } ioi }

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:57:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d", &n, &d, &m);
                              ^
jobs.cpp:59:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a[i].f);
                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...