Submission #302923

#	Time	Username	Problem	Language	Result	Execution time	Memory
302923		mohamedsobhi777	Cave (IOI13_cave)	C++14	0 / 100	5 ms	896 KiB

cave

#include "cave.h"
#include <vector>
#include<bits/stdc++.h>
 
using namespace std ; 
 
int n ; 
int *pos, *loc, *tmp ;  
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] ; 
        tmp = new int[N] ; 
        memset(pos , 0 , sizeof(int) * N) ; 
        memset(loc , 0 , sizeof(int) * N) ;
        memset(tmp , 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) ;
        int *q1 , *q2 ; 
        q1 = new int(sizeof(int) * n) ; 
        q2 = new int(sizeof(int) * n) ; 
 
        for(int i = 0 ;i < n;i++)
                q1[i] = qu[i] ; 
        for(auto u : vec)
                qu[u] = 1 ;
        int ret2 = tryCombination(qu) ; 
        for(int i = 0 ;i < n;i++)
                q2[i] = qu[i] ; 
        if(ret > ret2){
                swap(q1 , q2) ; 
                swap(ret , ret2) ; 
        }
        bool ok = (ret2 > door && ret ==  door) || (ret == -1 && ret2 == door) ;
        if(ok){
                col = 0 ; 
                if(ret != door){
                        for(int i = 0 ;i < n;i++)
                                tmp[i] = q1[i] ; 
                }
                else if(ret2!= door) {
                        for(int i = 0 ;i < n; i++ )
                                tmp[i] = q2[i] ; 
                }
        }
        else
                col = 2 ; 
        return ok; 
}
 
void solve( vector<int> swi , int door){
        if(swi . size() == 1){
                if(col == 2 ){
                        col = 0 ; 
                        pos[swi[0]] = 0 ; 
                        if(tryCombination(pos) == door){
                                col^=1 ; 
                        }
                        pos[swi[0]] = col ; 
                }
                else{
                        pos[swi[0]] = tmp[swi[0]] ; 
                }
 
                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++ ;
                col = 2 ; 
                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]) ; 
        }
        col = 2; 
        if(go(LHS, door)){
                solve(LHS, door) ; 
        }else{
                solve(RHS, door) ; 
        }
 
}
 
void exploreCave(int N) {
        init(N); 
        for(int i = 0 ;i < n;i++){
                col = 2; 
                solve(btns , i) ;         
        }
 
        answer(pos , loc) ; 
}

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