Submission #1182363

#TimeUsernameProblemLanguageResultExecution timeMemory
1182363zaki98Cave (IOI13_cave)C++20
64 / 100
670 ms712 KiB
#include <bits/stdc++.h> #define vt vector #define sz(c) (c).size() using namespace std; #include "cave.h" vt<int> vS, vD, vDs; int tryC(vt<int> arr){ const int x = sz(arr); int S[x]; for (int i=0;i<x;i++) S[i] = arr[i]; int ans = tryCombination(S); return (ans== -1 ? x : ans); } vt<int> special(int x, int type, int n){ vt<int> res(n); for (int i=0;i<n;i++){ if (i < x) res[i] = type; else res[i] = !type; } return res; } // log (n) int find_door(vt<int>ind, int door, int type){ vt<int> copy = vS; int n = sz(vS); int len = count_if(ind.begin(), ind.end(), [](int x){ return x != -1; }); int l=0,r=len-1; while(l<r){ int m = l + (r-l+1)/2; vt<int> x = special(m, type, len); int cur=0; for (int i=0;i<n;i++){ if (ind[i] != -1 && cur < x.size() && ind[i] < copy.size()) {copy[ind[i]] = x[cur];cur++;} } int ans = tryC(copy); if (ans <= door){ l = m; } else { r = m-1; } } int cur=0,res=0; for (int i=0;i<n;i++){ if (cur == l && ind[i] != -1) break; if (ind[i] != -1) cur++; res++; } // cout << "finding door" << door << " of type " << type; // cout << " for indices :"; // for (int i=0;i<n;i++) if (ind[i]!=-1) cout << ind[i] << " "; cout << ", "; // cout << "answer is :" << res << endl; return res; }; void exploreCave(int n) { int S[n], D[n], Ds[n]; vS.resize(n);vD.resize(n);vDs.resize(n); // Correct state of lever i, door mapped to lever i, state of door i for (int i=0;i<n;i++){ S[i] = 0; vS[i] = 0; D[i] = -1; vD[i] = -1; Ds[i] = -1; vDs[i] = -1; } vt<int> ind(n); iota(ind.begin(), ind.end(), 0); int x = tryC(vS); for (int i=0;i<x;i++){ int f = find_door(ind, i, 0); vDs[i] = 0; ind[f] = -1; vD[f] = i; vS[f] = 0; } if (x < n) { int f = find_door(ind, x, 1); ind[f] = -1; vD[f] = x; vDs[x] = 1; vS[f] = 1; } for (int i=x+1;i<n;i++){ int x = tryC(vS); bool type; if (x == i) type = 1; else type = 0; int f = find_door(ind, i, type); ind[f] = -1; vD[f] = i; vDs[x] = type; vS[f] = type; } /* Recover for (int i=0;i<n;i++) { S[D[i]] = Ds[D[i]]; } */ for (int i=0;i<n;i++) D[i] = vD[i]; for (int i=0;i<n;i++) S[i] = vS[i]; answer(S, D); }
#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...