This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
#define F first
#define S second
typedef vector<ii> vii;
typedef vector<vii> vvii;
#include "cave.h"
int queryArray[5010], queryArray2[5010];
class Solver{
private:
ll n;
vi doorOf, on, isFound, possibleSwitches;
void makeRandomOn(){
for (ll i = 0; n > i; i++){
if (!isFound[i]){
on[i] = rand()%2;
}
}
}
ll tryComb(vi comb){
for (ll i = 0; n > i; i++){
queryArray[i] = comb[i];
}
ll res = tryCombination(queryArray);
cout << "comb tried: ";
for (ll i = 0; n > i; i++){
cout << queryArray[i] << ' ';
}
cout << "res: " << res << endl;
return res;
}
void setSwitchDoor (ll swtch, ll door){
cout << "switch: " << swtch << " door: " << door << endl;
on[swtch] = 1-on[swtch];
isFound[swtch] = 1;
doorOf[swtch] = door;
vi newPossible;
for (auto i: possibleSwitches){
if (i != swtch) newPossible.push_back(i);
}
possibleSwitches = newPossible;
}
public:
Solver(ll n): n(n){
doorOf.assign(n,-1);
on.assign(n,0);
isFound.assign(n,0);
for (ll i = 0; n > i ; i++)
possibleSwitches.push_back(i);
}
void solve(){
for (ll door = 0; n > door; door++){
// make sure that last seen door is equal to 'door' variable
ll res;
cout << "for equal to door: \n";
do{
makeRandomOn();
res = tryComb(on);
/*
for (auto i: on) cout << i << ' ';
cout << "res: " << res;
cout << endl;
*/
}while (res != door);
//cout << endl;
cout << "for binary search: \n";
ll lo = 0, hi = possibleSwitches.size(), md;
vi curOn;
while (hi >= lo){
md = (lo+hi)/2;
if (hi == lo) break;
curOn = on;
for (ll i = lo; md >= i; i++){
curOn[possibleSwitches[i]] = 1-curOn[possibleSwitches[i]];
}
res = tryComb(curOn);
if (res == door){
lo = md+1;
}else{
hi = md;
}
}
setSwitchDoor(possibleSwitches[md], door);
}
for (ll i = 0; n > i; i++){
queryArray[i] = on[i];
queryArray2[i] = doorOf[i];
}
answer(queryArray, queryArray2);
}
};
void exploreCave(int n) {
Solver mySolver(n);
mySolver.solve();
}
Compilation message (stderr)
cave.cpp: In member function 'void Solver::solve()':
cave.cpp:102:46: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
102 | setSwitchDoor(possibleSwitches[md], door);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |