# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
962672 | 2024-04-14T06:39:51 Z | serkanrashid | Cave (IOI13_cave) | C++14 | 0 ms | 0 KB |
#include "cave.h" #include <bits/stdc++.h> using namespace std; const int maxn = 5005; int *s,*d; int tekdoor; int rec(vector<int>pos) { if(pos.size()==1) return pos[0]; int mid = (pos.size()-1)/2; for(int j = 0; j <= mid; j++) s[pos[j]] ^= 1; int ch = tryCombination(s); vector<int>nb; if(ch == i) { for(int j = mid+1; j < pos.size(); j++) nb.push_back(pos[j]); return rec(nb); } for(int j = 0; j <= mid; j++) { s[pos[j]] ^= 1; nb.push_back(pos[j]); } return rec(nb); } void exploreCave(int N) { int ch; s = new int[N]; d = new int[N]; for(int i = 0; i < N; i++) d[i] = -1; for(int i = 0; i < N; i++) { vector<int>pos; for(int j = 0; j < N; j++) { if(d[j] == -1) { s[j] = 0; pos.push_back(j); } } ch = tryCombination(s); if(ch != i) { for(int j = 0; j < N; j++) if(d[j] == -1) s[j] = 1; } int idx = rec(pos); d[idx] = i; s[idx] ^= 1; } for(int i = 0; i < N; i++) s[i] ^= 1; answer(s,d); }