이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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();
}
컴파일 시 표준 에러 (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... |