이 제출은 이전 버전의 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; comb.size() > i; i++){
queryArray[i] = comb[i];
}
return tryCombination(queryArray);
}
void setSwitchDoor (ll swtch, ll door){
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;
do{
makeRandomOn();
res = tryComb(on);
}while (res != door);
ll lo = 0, hi = possibleSwitches.size(), md;
vi curOn;
while (hi > lo){
md = (lo+hi)/2;
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 'll Solver::tryComb(vi)':
cave.cpp:31:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
31 | for (ll i = 0; comb.size() > i; i++){
| ~~~~~~~~~~~~^~~
cave.cpp: In member function 'void Solver::solve()':
cave.cpp:87:46: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
87 | 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... |