Submission #239842

#	Time	Username	Problem	Language	Result	Execution time	Memory
239842		Dremix10	Cave (IOI13_cave)	C++17	100 / 100	237 ms	632 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)


void exploreCave(int N) {
    //cout<<N<<endl;
    int query[N];

    int i,j;

    int switches[N];
    for(i=0;i<N;i++)
        switches[i]=-1;

    int door[N];int toSwitch[N];
    for(i=0;i<N;i++){
        door[i]=-1;
        toSwitch[i]=-1;
    }

//    cout<<last<<endl;



    for(i=0;i<N;i++){

        for(j=0;j<N;j++)
            if(switches[j]==-1)
                query[j]=0;
            else
                query[j]=switches[j];

        //for(j=0;j<N;j++)
        //    cout<<query[j]<<" ";
        //cout<<endl;

        int last=tryCombination(query);

        bool open=true;
        if(last==i)
            open=false;
        //cout<<last<<" "<<open<<endl;
        int l=0,r=N-1;
        //int mm=-1;
        //int one=-1;
        //cout<<open<<" "<<i<<endl;
        while(l<r){
            int mid=(l+r)/2;
            for(j=l;j<=mid;j++)
                if(switches[j]==-1)
                query[j]^=1;

            int x=tryCombination(query);
            //cout<<l<<" "<<r<<" "<<mid<<" "<<x<<" "<<open<<endl;
            if((open && x<=i && x!=-1) || (!open && (x>i || x==-1))){
                r=mid;
                //mm=mid;
                open^=1;
                //if((query[r]==1 && !open) || (query[r]==0 && open))
                //    one=true;
                //else
                //    one=false;
            }
            else
                l=mid+1;
        }
        int mm=r;
        if(r-l==1){
            if(switches[l]==-1)
                query[l]^=1;
            int x=tryCombination(query);
            if((open && x<=i && x!=-1) || (!open && (x>i || x==-1))){
                mm=l;
                open^=1;
            }
        }
        //cout<<"ans"<<endl;
        //cout<<open<<" "<<mm<<" "<<query[mm]<<endl;
        //cout<<l<<" "<<r<<endl;
        bool one;
        door[mm]=i;
        if((query[mm]==1 && open) || (query[mm]==0 && !open))
            one=true;
        else
            one=false;
        if(one)
            switches[mm]=1;
        else
            switches[mm]=0;

        //cout<<"ans "<<i<<": "<<mm<<" "<<switches[mm]<<endl;
        //cout<<switches[mm]<<endl;

    }

    answer(switches,door);


}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:26:21: warning: variable 'toSwitch' set but not used [-Wunused-but-set-variable]
     int door[N];int toSwitch[N];
                     ^~~~~~~~

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