Submission #302893

#	Time	Username	Problem	Language	Result	Execution time	Memory
302893		mohamedsobhi777	Cave (IOI13_cave)	C++14	51 / 100	346 ms	740 KiB

cave

#include "cave.h"
#include <vector>
#include<bits/stdc++.h>

using namespace std ; 

int n ; 
int *pos, *loc; 
bool vis[10000] ; 
int it, col ;
void flip(){
        for(int i = 0 ;i < n ;i++)
                pos[i]^=1 ; 
}

vector<int> btns ; 

void init(int N){
        n = N ; 
        pos = new int[N] ;
        loc = new int[N] ; 
        memset(pos , 0 , sizeof(int) * N) ; 
        memset(loc , 0 , sizeof(int) * N) ;
        for(int i = 0 ;i < N ;i++)
                btns.push_back(i) ;
}

int go(vector<int> vec, int door){
        int ret = n ; 
        int *qu = pos ; 
        for(auto u : vec)
                qu[u] = 0 ;
        ret = tryCombination(qu) ;
        if(ret != door)
                col = 0 ;  
      
        for(auto u : vec)
                qu[u] = 1 ;
        int ret2 = tryCombination(qu) ; 
        if(ret2 != door)
                col = 1; 
        if(ret > ret2)
                swap(ret , ret2) ; 

        return (ret2 > door && ret ==  door) || (ret == -1 && ret2 == door) ; 
}

void solve( vector<int> swi , int door){
        if(swi . size() == 1){
                pos[swi[0]] = col ; 
                if(tryCombination(pos) == door){
                        col^= 1; 
                        pos[swi[0]] ^= 1 ; 
                }
                loc[ swi[0] ] = it ; 
                for(int i = 0 ;i < (int) btns.size() ; ++ i){
                        if(btns[i] == swi[0]){
                                btns.erase(btns.begin() + i) ;
                                break ; 
                        }
                }
                it++ ;
                return ; 
        }
        vector<int> LHS , RHS ; 
        int sz = (int) swi.size() ; 
        for(int i = 0 ;i < sz ;i ++){
                if(i < sz / 2)
                        LHS.push_back(swi[i]) ; 
                else
                        RHS.push_back(swi[i]) ; 
        }

        if(go(LHS, door)){
                solve(LHS, door) ; 
        }else{
                solve(RHS, door) ; 
        }

}

void exploreCave(int N) {
        init(N); 
        for(int i = 0 ;i < n;i++){
                solve(btns , i) ;         
        }

        answer(pos , loc) ; 
}

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