Submission #388007

#	Time	Username	Problem	Language	Result	Execution time	Memory
388007		ivan24	Cave (IOI13_cave)	C++14	100 / 100	1148 ms	584 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; 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);
      |                                              ^

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