#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) ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
284 ms |
632 KB |
too much calls on tryCombination() |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
346 ms |
740 KB |
too much calls on tryCombination() |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
380 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
380 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
91 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
92 ms |
384 KB |
Output is correct |
24 |
Correct |
92 ms |
384 KB |
Output is correct |
25 |
Correct |
93 ms |
504 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
93 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
91 ms |
504 KB |
Output is correct |
31 |
Correct |
93 ms |
504 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
93 ms |
384 KB |
Output is correct |
36 |
Correct |
92 ms |
504 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
284 ms |
632 KB |
too much calls on tryCombination() |
2 |
Halted |
0 ms |
0 KB |
- |