Submission #502710

#	Time	Username	Problem	Language	Result	Execution time	Memory
502710		Lobo	Cave (IOI13_cave)	C++17	100 / 100	878 ms	544 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
using namespace std;

/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 

void exploreCave(ii n) {

    ii s[n], d[n];
    for(ii i = 0; i < n; i++) {
        s[i] = -1;
        d[i] = 0;
    }

    for(ii i = 0; i < n; i++) {
        ii sq[n];
        for(ii j = 0; j < n; j++) {
            if(s[j] == -1)
                sq[j] = 0;
            else 
                sq[j] = s[j];
        }

        ii ok = tryCombination(sq);
        //0 -> door i closed
        //1 -> door i open
        if(ok == i) ok = 0;
        else ok = 1;

        ii l = 0;
        ii r = n-1;
        ii ansbs;
        while(l <= r) {
            ii mid = (l+r)/2;
            //intervalo (l,mid) muda pra 1

            for(ii j = 0; j < n; j++) {
                if(s[j] == -1) {
                    if(l <= j && j <= mid) sq[j] = 1;
                    else sq[j] = 0;
                }
                else 
                    sq[j] = s[j];
            }

            ii ok1 = tryCombination(sq);
            if(ok1 == i) ok1 = 0;
            else ok1 = 1;

            if(ok1 == ok) {
                //swt for i in (mid+1,r);
                l = mid+1;
            }
            else {
                ansbs = mid;
                r = mid-1;
            }

        }

        //swt ansbs = door i
        d[ansbs] = i;
        //ok = 0 -> s[ansbs] = 0 -> door i is closed -> s[ansbs] = 1
        if(ok == 0) s[ansbs] = 1;
        else s[ansbs] = 0;
    }

    answer(s, d);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(ii)':
cave.cpp:51:12: warning: 'ansbs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |         ii ansbs;
      |            ^~~~~

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