Submission #482645

#	Time	Username	Problem	Language	Result	Execution time	Memory
482645		gmyu	Cave (IOI13_cave)	C++14	64 / 100	255 ms	376 KiB

cave

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI13_cave
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 300007
#define MAXE 100007

bool debug=false;

void printKey(int s[], int d[], int N) {
    cout << "On/off ";
    for(int i=0; i<N; i++) cout << s[i] << " ";
    cout << endl << "Door   ";
    for(int i=0; i<N; i++) cout << d[i] << " ";
    cout << endl;
}

#include "cave.h"
void exploreCave(int N) {
    int corSet[N],corDoor[N];
    for(int i=0;i<N;i++) { corSet[i]=0; corDoor[i]=-1;}

    for(int cur = 0; cur <N; cur++) {
        int l=0, r=N-1;
        for(int i=l; i<=r; i++) if(corDoor[i] == -1) corSet[i] = 0;
        int ans = tryCombination(corSet);
        int key;
        while(l<r) {
            if(debug) printKey(corSet, corDoor, N);
            if(debug) cout << " .. for door " << cur << ": " << ans << ":" << l << " " << r ;
            // make sure the door is open
            if(ans==-1 || ans>cur) {
                // door opened, as I wanted
            } else {
                // the flip will make the door open
                for(int i=l; i<=r; i++) if(corDoor[i] == -1) corSet[i] = !corSet[i];
                if(debug) {
                    cout << " open " << tryCombination(corSet) << "; " << endl;
                    printKey(corSet, corDoor, N);
                }
            }

            // try half of it to close this door
            int m = (l+r)/2;
            for(int i=l; i<=m; i++) if(corDoor[i] == -1) corSet[i] = !corSet[i];
            ans = tryCombination(corSet);
            if(ans == cur) {
                // successfully closed it. The right door is in this half
                r=m;
                key = !corSet[l];
            } else {
                l=m+1;
                key = corSet[l];
            }
            if(debug) cout << " ==> " << ans << ":" << l << " " << r << endl;
        }
        corDoor[l] = cur;
        corSet[l] = key;

        if(debug) {
            cout << "answer -- " << endl;
            printKey(corSet, corDoor, N);
        }

    }

    if(debug) printKey(corSet, corDoor, N);
    answer(corSet, corDoor);

}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:89:19: warning: 'key' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |         corSet[l] = key;
      |         ~~~~~~~~~~^~~~~

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