oj.uz

Submission #74131

# Submission time Handle Problem Language Result Execution time Memory
74131 2018-08-30T08:41:25 Z admin Dancing Elephants (IOI11_elephants) C++17
100 / 100
 4496 ms 120036 KB 
#include<stdio.h>
#include<math.h>
 
int N, L, Q;
 
#define bN 390
#define N_ 150000
 
int tmp[N_+1], tmp2[N_+1];
 
class Elephant {
    int bucket [bN+1][2*bN+5];
    int cnt [bN+1];
    int cameras [bN+1][2*bN+5];
    int end [bN+1][2*bN+5];
    int number [bN+1][2*bN+5];
    int wh [N_+1];
 
    int bn, bl;
    int jcnt;
 
    void solve(int num){ // bucket[num]에 대해 cameras, end 문제 해결
        int *b = bucket[num], *c = cameras[num], *e = end[num];
        int i, j = cnt[num] + 1; c[j] = 0;
        for(i = cnt[num]; i > 0; i--){
            while(b[--j] - b[i] > L); j++;
            c[i] = c[j] + 1; 
            if(j <= cnt[num]) e[i] = e[j];
            else e[i] = b[i] + L;
        }
    }
 
    void init(){
        int i, j, tn = 0;
        for(i=1; i<=bn; i++){
            for(j=1; j<=cnt[i]; j++){
                tmp[++tn] = bucket[i][j];
                tmp2[tn] = number[i][j];
            }
            cnt[i] = 0;
        }
        bn = 1;
        for(i=1; i<=N; i++){
            bucket[bn][++cnt[bn]] = tmp[i];
            number[bn][cnt[bn]] = tmp2[i];
            wh[tmp2[i]] = bn;
            if(cnt[bn] == bl) solve(bn++);
        }
        if(cnt[bn]) solve(bn); else bn--;
    }
 
    void find_by_num(int e,int &bx,int &by){
        bx = wh[e];
        for(by=1; by<=cnt[bx]; by++){
            if(number[bx][by] == e) break;
        }
    }
 
    void find_by_pos (int x,int &bx,int &by){
        for(bx=1; bx<=bn; bx++){
            if(bucket[bx][cnt[bx]] >= x) break;
        }
        if(bx > bn) bx = bn;
        for(by=1; by<=cnt[bx]; by++){ if(bucket[bx][by] >= x) break; } 
    }
 
    int solve_cameras (){
        int i, x = bucket[1][1] + L, ret = 1;
        for(i=1; i<=bn; i++){
            int left=1, right=cnt[i], last = -1;
            while(left <= right){
                int mid = (left+right)>>1;
                if(bucket[i][mid] > x){
                    last = mid; right = mid - 1;
                }else left = mid + 1;
            }
            if(last > 0){
                ret += cameras[i][last];
                x = end[i][last];
            }
        }
        return ret;
    }
public:
    void input(int *X){
        int i; bn = 1; bl = 1+(int)sqrt((double)N);
        for(i=1; i<=N; i++){
            bucket[bn][++cnt[bn]] = X[i-1];
            number[bn][cnt[bn]] = i; wh[i] = bn;
            if(cnt[bn] == bl) solve(bn++);
        }
        if(cnt[bn]) solve(bn); else bn--;
    }
 
    int jump(int e, int p){ //e번 코끼리가 p 위치로 jump
        int ex, ey, px, py, i;
 
        find_by_num(e, ex, ey);
        for(i=ey; i<cnt[ex]; i++){
            bucket[ex][i] = bucket[ex][i+1];
            number[ex][i] = number[ex][i+1];
        }
        cnt[ex]--; solve(ex);
 
        find_by_pos(p, px, py); ++cnt[px];
        for(i=cnt[px]; i>py; i--){
            bucket[px][i] = bucket[px][i-1];
            number[px][i] = number[px][i-1];
        }
        bucket[px][py] = p; number[px][py] = e; 
        wh[e] = px; solve(px);
 
        if(++jcnt == bl) init(), jcnt = 0;
 
        return solve_cameras();
    }
};
 
Elephant ele;
 
void init (int n, int l, int *X) {
 N = n; L = l;
    ele.input(X);
}
 
int update (int i, int y) {
 return ele.jump(i+1, y);
}

Compilation message

elephants.cpp: In member function 'void Elephant::solve(int)':
elephants.cpp:26:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
             while(b[--j] - b[i] > L); j++;
             ^~~~~
elephants.cpp:26:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
             while(b[--j] - b[i] > L); j++;
                                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 254 ms 3744 KB Output is correct
8 Correct 298 ms 5096 KB Output is correct
9 Correct 434 ms 8216 KB Output is correct
10 Correct 422 ms 9664 KB Output is correct
11 Correct 445 ms 10872 KB Output is correct
12 Correct 708 ms 12488 KB Output is correct
13 Correct 409 ms 13512 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 254 ms 3744 KB Output is correct
8 Correct 298 ms 5096 KB Output is correct
9 Correct 434 ms 8216 KB Output is correct
10 Correct 422 ms 9664 KB Output is correct
11 Correct 445 ms 10872 KB Output is correct
12 Correct 708 ms 12488 KB Output is correct
13 Correct 409 ms 13512 KB Output is correct
14 Correct 366 ms 13584 KB Output is correct
15 Correct 488 ms 15344 KB Output is correct
16 Correct 1040 ms 18476 KB Output is correct
17 Correct 1254 ms 21396 KB Output is correct
18 Correct 1311 ms 23424 KB Output is correct
19 Correct 748 ms 25528 KB Output is correct
20 Correct 1259 ms 27568 KB Output is correct
21 Correct 1192 ms 29464 KB Output is correct
22 Correct 713 ms 31204 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 254 ms 3744 KB Output is correct
8 Correct 298 ms 5096 KB Output is correct
9 Correct 434 ms 8216 KB Output is correct
10 Correct 422 ms 9664 KB Output is correct
11 Correct 445 ms 10872 KB Output is correct
12 Correct 708 ms 12488 KB Output is correct
13 Correct 409 ms 13512 KB Output is correct
14 Correct 366 ms 13584 KB Output is correct
15 Correct 488 ms 15344 KB Output is correct
16 Correct 1040 ms 18476 KB Output is correct
17 Correct 1254 ms 21396 KB Output is correct
18 Correct 1311 ms 23424 KB Output is correct
19 Correct 748 ms 25528 KB Output is correct
20 Correct 1259 ms 27568 KB Output is correct
21 Correct 1192 ms 29464 KB Output is correct
22 Correct 713 ms 31204 KB Output is correct
23 Correct 3245 ms 39840 KB Output is correct
24 Correct 3466 ms 44748 KB Output is correct
25 Correct 2628 ms 49868 KB Output is correct
26 Correct 2825 ms 54908 KB Output is correct
27 Correct 2895 ms 59856 KB Output is correct
28 Correct 546 ms 59856 KB Output is correct
29 Correct 515 ms 59856 KB Output is correct
30 Correct 572 ms 62416 KB Output is correct
31 Correct 516 ms 65320 KB Output is correct
32 Correct 3009 ms 75976 KB Output is correct
33 Correct 2411 ms 79808 KB Output is correct
34 Correct 2559 ms 84496 KB Output is correct
35 Correct 2469 ms 89552 KB Output is correct
36 Correct 2853 ms 93876 KB Output is correct
37 Correct 3660 ms 98848 KB Output is correct
38 Correct 2620 ms 102416 KB Output is correct
39 Correct 2640 ms 107120 KB Output is correct
40 Correct 2703 ms 110836 KB Output is correct
41 Correct 4496 ms 115400 KB Output is correct
42 Correct 4402 ms 120036 KB Output is correct