Submission #97843

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
97843	2019-02-18T21:07:18 Z	RezwanArefin01	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	744 ms	15148 KB

jobs

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10; 
vector<int> p[N];
int t[N << 2], sz[N] = {10*N}, n, d, m, x, ans; 

void build(int node, int l, int r) {
    t[node] = l;
    if(l == r) return; 
    int m = l + r >> 1; 
    build(node << 1, l, m); 
    build(node << 1 | 1, m + 1, r);
}
int query(int node, int l, int r, int i, int j) {
    if(r < i || l > j) return 0; 
    if(i <= l && r <= j) return t[node]; 
    int m = l + r >> 1;
    int q1 = query(node << 1, l, m, i, j); 
    int q2 = query(node << 1 | 1, m + 1, r, i, j); 
    return sz[q1] <= sz[q2] ? q1 : q2; 
}
void update(int node, int l, int r, int i, int id) {
    if(l == r) {
        ans = max(ans, ++sz[l]);  
        p[l].push_back(id); 
        return; 
    } 
    int m = l + r >> 1; 
    if(i <= m) update(node << 1, l, m, i, id); 
    else update(node << 1 | 1, m + 1, r, i, id); 
    int q1 = t[node << 1], q2 = t[node << 1 | 1];
    t[node] = sz[q1] <= sz[q2] ? q1 : q2; 
}
int main() {
    scanf("%d %d %d", &n, &d, &m); 
    build(1, 1, n); 
    for(int i = 1; i <= m; i++) {
        scanf("%d", &x); 
        update(1, 1, n, query(1, 1, n, x, x + d), i); 
    }
    printf("%d\n", ans); 
    for(int i = 1; i <= n; i++) {
        for(int x : p[i]) printf("%d ", x); 
        puts("0"); 
    }
}

Compilation message

jobs.cpp: In function 'void build(int, int, int)':
jobs.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
jobs.cpp: In function 'int query(int, int, int, int, int)':
jobs.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
jobs.cpp: In function 'void update(int, int, int, int, int)':
jobs.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
jobs.cpp: In function 'int main()':
jobs.cpp:40:10: 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:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x); 
         ~~~~~^~~~~~~~~~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	4396 KB	Output is correct
2	Correct	52 ms	4312 KB	Output is correct
3	Correct	44 ms	4340 KB	Output is correct
4	Correct	52 ms	4468 KB	Output is correct
5	Correct	47 ms	4348 KB	Output is correct
6	Correct	46 ms	4344 KB	Output is correct
7	Correct	48 ms	4468 KB	Output is correct
8	Correct	43 ms	4340 KB	Output is correct
9	Incorrect	81 ms	5368 KB	Output isn't correct
10	Incorrect	61 ms	5404 KB	Output isn't correct
11	Incorrect	61 ms	4216 KB	Output isn't correct
12	Incorrect	109 ms	5768 KB	Output isn't correct
13	Incorrect	150 ms	7408 KB	Output isn't correct
14	Incorrect	366 ms	9052 KB	Output isn't correct
15	Incorrect	236 ms	8848 KB	Output isn't correct
16	Incorrect	492 ms	10660 KB	Output isn't correct
17	Incorrect	744 ms	13972 KB	Output isn't correct
18	Incorrect	455 ms	13304 KB	Output isn't correct
19	Incorrect	556 ms	15148 KB	Output isn't correct
20	Incorrect	576 ms	14072 KB	Output isn't correct