oj.uz

Submission #588529

# Submission time Handle Problem Language Result Execution time Memory
588529 2022-07-03T13:18:06 Z updown1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 285 ms 17184 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 1, M+1)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=1000000;//, INF=1000000000000000000;
///500,000,000
int D, N, M;
pair<int, int> inp[MAXN];
 
bool works(int m) {
    int day = 1;
    int lef = m;
    ffi {
        if (inp[i].a > day) day=inp[i].a, lef = m;
        if (inp[i].a + D < day) return false;
        lef--;
        if (lef == 0) day++, lef=m;
    }
    return true;
}
 
int main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> M >> D >> N;
    ffi {cin >> inp[i].a; inp[i].b = i+1;}
    sort(inp, inp+N);
    int a=1, b=N;
    while (a != b) {
        int mid = (a+b)/2;
        if (works(mid)) b = mid;
        else a = mid+1;
    }
    w<< a<<e;
    int at = 0;
    ffj {
        int cnt = 0;
        while (at != N && inp[at].a <= j && cnt <a) {
            cnt++;
            w<< inp[at].b<< " ";
            at++;
        }
        w<< 0<<e;
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2004 KB Output is correct
2 Correct 18 ms 1924 KB Output is correct
3 Correct 19 ms 1916 KB Output is correct
4 Correct 23 ms 1924 KB Output is correct
5 Correct 17 ms 1996 KB Output is correct
6 Correct 16 ms 1952 KB Output is correct
7 Correct 17 ms 1924 KB Output is correct
8 Correct 17 ms 1992 KB Output is correct
9 Correct 30 ms 2108 KB Output is correct
10 Correct 30 ms 2144 KB Output is correct
11 Correct 26 ms 2060 KB Output is correct
12 Correct 58 ms 3812 KB Output is correct
13 Correct 74 ms 5804 KB Output is correct
14 Correct 104 ms 8068 KB Output is correct
15 Correct 164 ms 9420 KB Output is correct
16 Correct 155 ms 11984 KB Output is correct
17 Correct 189 ms 13940 KB Output is correct
18 Correct 208 ms 15104 KB Output is correct
19 Correct 285 ms 17184 KB Output is correct
20 Correct 183 ms 13868 KB Output is correct