oj.uz

Submission #10426

# Submission time Handle Problem Language Result Execution time Memory
10426 2014-10-27T23:37:59 Z gs14004 Cave (IOI13_cave) C++
51 / 100
 349 ms 520 KB 
#include "cave.h"

int S[5005], D[5005];
int visited[5005];

void change(int s, int e){
    for(int i=s; i<=e; i++){
        if(!visited[i]) S[i] ^= 1;
    }
}

int find(int pos, int n){
    int s = 0, e = n-1;
    if(tryCombination(S) != pos) change(0,n-1);
    while (s != e) {
        int m = (s+e)/2;
        change(s,m);
        int t = tryCombination(S);
        change(s,m);
        if(pos != t) e = m;
        else s = m+1;
    }
    return s;
}

void exploreCave(int n){
    if(tryCombination(S)) change(0,n-1);
    for (int i=0; i<n; i++) {
        int pos = find(i,n);
        D[pos] = i;
        visited[pos] = 1;
        if(tryCombination(S) == i) S[pos] ^= 1;
    }
    answer(S,D);
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 520 KB Output is correct
2 Correct 165 ms 512 KB Output is correct
3 Incorrect 267 ms 468 KB too much calls on tryCombination()
4 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 271 ms 512 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 5 ms 400 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 400 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 400 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 64 ms 448 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 6 ms 336 KB Output is correct
9 Correct 80 ms 384 KB Output is correct
10 Correct 58 ms 444 KB Output is correct
11 Correct 61 ms 384 KB Output is correct
12 Correct 6 ms 332 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 42 ms 396 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 41 ms 456 KB Output is correct
17 Correct 39 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 6 ms 512 KB Output is correct
21 Correct 81 ms 440 KB Output is correct
22 Correct 55 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 476 KB Output is correct
2 Correct 177 ms 480 KB Output is correct
3 Incorrect 349 ms 496 KB too much calls on tryCombination()
4 Halted 0 ms 0 KB -