Submission #387993

#	Time	Username	Problem	Language	Result	Execution time	Memory
387993		ivan24	Cave (IOI13_cave)	C++14	12 / 100	2076 ms	580 KiB

cave

#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();
}

Compilation message (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);
      |                                              ^

• Subtask 1: 12 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24