Submission #441853

#	Time	Username	Problem	Language	Result	Execution time	Memory
441853		Idkwhoami	Cave (IOI13_cave)	C++17	0 / 100	211 ms	452 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;

void f(int v[], int x, int n){
    for(int i =0;i<n;i++)cout << v[i]; 
    cout << "\nx = " << x << '\n';
}
void exploreCave(int n) {
    // cout << n ;
    int v[n], ans[n], d[n];
    for(int i =0;i<n;i++){
        v[i] = 0;
        ans[i] = -1;
    }
    int curr = 0;
    while(curr != n-1){
        int l = 0, r = n-1, type = 0, x;

        for(int i =0;i<n;i++)if(ans[i] == -1)v[i] = type;

        // int test[n] = {0,0,0,0};

        x = tryCombination(v);
        // f(v, x, n);


        if(x == -1 || x <= curr)type = 1;

        // cout << "type: " << type << '\n';

        while(l < r){
            // cout << l << " " << r << " ";
            int temp[n]; 

            for(int i = 0;i<n;i++)temp[i] = v[i];

            int mid = (l+r)/2;

            for(int i = l;i<=mid;i++)if(ans[i] == -1)temp[i] = type;
            for(int i = mid+1;i<=r;i++)if(ans[i] == -1)temp[i] = !type;


            x = tryCombination(temp);
            // f(temp, x, n);

            if(x >= curr+1 || x == -1){
                r = mid;
            }
            else{
                l = mid+1;
            }        
        }
        v[l] = ans[l] = type;
        d[l] = curr;
        // for(auto i:ans)cout << i; 
        // cout << "\n\n";
        curr++;
    }   
    int index = 0;
    for(int i = 0;i<n;i++)if(ans[i] == -1)index = i;
    v[index] = 0;
    d[index] = n-1;    
    int x = tryCombination(v);
    if(x == -1){
        ans[index] = 0;
        answer(ans, d);
    }
    else{
        ans[index] = 1;
        answer(ans, d);
    }    
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24