Submission #1077739

#TimeUsernameProblemLanguageResultExecution timeMemory
1077739TheQuantiXCave (IOI13_cave)C++17
100 / 100
264 ms852 KiB
#include <bits/stdc++.h> #include "cave.h" // #include "grader.h" using namespace std; using ll = long long; ll n, m, q, k, x, y, a, b, c; ll func(vector<int> &st, int *v, int open, int x) { // for (auto i : st) { // cout << i << ' '; // } // cout << '\n'; // cout << '\t' << open << '\n'; if (st.size() == 1) { return *st.begin(); } ll sz = st.size() / 2; vector<int> st1, st2; for (int i = 0; i < sz; i++) { st1.push_back(st[st.size() - 1]); st.pop_back(); } while (st.size() > 0) { st2.push_back(st[st.size() - 1]); st.pop_back(); } for (auto i : st1) { v[i] = open; } bool fl = 0; // for (int j = 0; j < n; j++) { // cout << v[j] << ' '; // } // cout << '\n'; ll tr = tryCombination(v); // cout << '\t' << tr << '\n'; if (tr == x) { fl = 1; } for (auto i : st1) { v[i] = 1 - open; } if (fl) { swap(st1, st2); } // cout << '\n'; return func(st1, v, open, x); } void exploreCave(int N) { n = N; int *ans1 = new int[n]; int *ans2 = new int[n]; vector<int> st; for (int i = 0; i < n; i++) { st.push_back(i); } vector<bool> open(n); vector<int> point(n, -1); int *v = new int[n]; for (int i = 0; i < n; i++) { // cout << i << endl; for (int j = 0; j < n; j++) { v[j] = 0; } for (int j = 0; j < n; j++) { if (point[j] != -1) { v[point[j]] = open[j]; } } // for (int j = 0; j < n; j++) { // cout << v[j] << ' '; // } // cout << '\n'; ll tr = tryCombination(v); // cout << '\t' << tr << '\n'; if (tr == i) { open[i] = 1; } else { open[i] = 0; } for (auto j : st) { v[j] = 1 - open[i]; } vector<int> st1 = st; ll x = func(st1, v, open[i], i); point[i] = x; st1.clear(); for (auto i : st) { if (i != x) { st1.push_back(i); } } swap(st, st1); } // for (int i = 0; i < n; i++) { // cout << open[i] << ' ' << point[i] << '\n'; // } // cout << '\n'; for (int i = 0; i < n; i++) { ans2[point[i]] = i; ans1[point[i]] = open[i]; } // for (int i = 0; i < n; i++) { // cout << ans1[i] << ' ' << ans2[i] << '\n'; // } answer(ans1, ans2); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...