oj.uz

Submission #68788

# Submission time Handle Problem Language Result Execution time Memory
68788 2018-08-18T11:35:13 Z someone_aa Cave (IOI13_cave) C++17
12 / 100
 309 ms 544 KB 
#include <bits/stdc++.h>
#include "cave.h"

using namespace std;

const int maxn = 5100;
int open[maxn], sw[maxn], n;
int f[maxn], bq;

int curr[maxn];


bool valid(int l, int r) {
    bool valid = false;
    for(int i=l;i<=r;i++) {
        if(f[i] == -1) valid = true;
    }
    return valid;
}

bool validq(int ind, int l, int r) {
    for(int i=l;i<=r;i++) {
        if(f[i] == -1) {
            curr[i] = 1;
        }
    }
    int ans = tryCombination(curr);

    for(int i=l;i<=r;i++) {
        if(f[i] == -1) {
            curr[i] = 0;
        }
    }


    if((bq <= ind && bq!=-1)&& (ans > ind || ans == -1)) return true;// otvorile su se vrata ss index ind
    else if((bq > ind || bq==-1) && ans <= ind) return true; // zatvorile su se tija vrata
    else return false;
}

void setind(int ind, int x) {
    curr[ind] = 1;
    int ans = tryCombination(curr);

    //cout<<"Connecting door: "<<x<<" with switch: "<<ind<<"\n";

    if(ans > x || ans == -1) {
        f[ind] = 1;
        curr[ind] = 1;
    }
    else if(ans == x) {
        f[ind] = 0;
        curr[ind] = 0;
    }
    /*cout<<"Connection done:\n";
    for(int i=0;i<n;i++) {
        cout<<curr[i]<<" ";
    } cout<<"\n";*/
}

void solve(int ind, int l, int r) {
    int mid = (l+r)/2;
    //cout<<ind<<": "<<l<<" "<<r<<"\n";
    if(l==r) {
        sw[l] = ind;
        setind(l, ind);
    }
    else {
        if(valid(l , mid)) {
            if(validq(ind, l, mid)) {
                solve(ind, l, mid);
            }
            else {
                solve(ind, mid+1, r);
            }
        }
        else {
            solve(ind, mid+1, r);
        }
    }
}

void exploreCave(int N) {
    n = N;
    memset(f,-1,sizeof(f));

    for(int i=0;i<N;i++) {
        bq = tryCombination(curr);
        /*cout<<"Before start:\n";
        for(int i=0;i<N;i++) {
            cout<<curr[i]<<" ";
        }cout<<"\n";
        for(int i=0;i<N;i++) {
            cout<<f[i]<<" ";
        } cout<<"\n";*/
        solve(i, 0, N-1);
    }
    //bq = tryCombination(curr);
    //cout<<validq(5, 0, 3);
    answer(curr, sw);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 504 KB Output is correct
2 Correct 104 ms 504 KB Output is correct
3 Correct 205 ms 512 KB Output is correct
4 Correct 94 ms 528 KB Output is correct
5 Correct 196 ms 516 KB Output is correct
6 Correct 170 ms 496 KB Output is correct
7 Correct 216 ms 488 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 192 ms 528 KB Output is correct
13 Correct 143 ms 508 KB Output is correct
14 Correct 180 ms 492 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 524 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 309 ms 544 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 183 ms 516 KB Output is correct
7 Incorrect 291 ms 508 KB too much calls on tryCombination()
8 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Incorrect 6 ms 460 KB Answer is wrong
12 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Incorrect 6 ms 460 KB Answer is wrong
12 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 504 KB Output is correct
2 Correct 104 ms 504 KB Output is correct
3 Correct 205 ms 512 KB Output is correct
4 Correct 94 ms 528 KB Output is correct
5 Correct 196 ms 516 KB Output is correct
6 Correct 170 ms 496 KB Output is correct
7 Correct 216 ms 488 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 192 ms 528 KB Output is correct
13 Correct 143 ms 508 KB Output is correct
14 Correct 180 ms 492 KB Output is correct
15 Correct 164 ms 524 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 309 ms 544 KB Output is correct
18 Correct 6 ms 512 KB Output is correct
19 Correct 6 ms 512 KB Output is correct
20 Correct 183 ms 516 KB Output is correct
21 Incorrect 291 ms 508 KB too much calls on tryCombination()
22 Halted 0 ms 0 KB -