oj.uz

Submission #49080

# Submission time Handle Problem Language Result Execution time Memory
49080 2018-05-22T00:32:53 Z updown1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 333 ms 32768 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 23 ms 2040 KB Output is correct
2 Correct 23 ms 2468 KB Output is correct
3 Correct 23 ms 2800 KB Output is correct
4 Correct 26 ms 3180 KB Output is correct
5 Correct 25 ms 3452 KB Output is correct
6 Correct 26 ms 3876 KB Output is correct
7 Correct 25 ms 4104 KB Output is correct
8 Correct 26 ms 4400 KB Output is correct
9 Correct 41 ms 4884 KB Output is correct
10 Correct 40 ms 5060 KB Output is correct
11 Correct 34 ms 5260 KB Output is correct
12 Correct 70 ms 7564 KB Output is correct
13 Correct 107 ms 10204 KB Output is correct
14 Correct 173 ms 13568 KB Output is correct
15 Correct 177 ms 17060 KB Output is correct
16 Correct 206 ms 21396 KB Output is correct
17 Correct 257 ms 26216 KB Output is correct
18 Correct 287 ms 30692 KB Output is correct
19 Correct 333 ms 32768 KB Output is correct
20 Correct 248 ms 32768 KB Output is correct