Submission #482631

#	Time	Username	Problem	Language	Result	Execution time	Memory
482631		gmyu	Cave (IOI13_cave)	C++14	0 / 100	47 ms	360 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;

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]=-1; corDoor[i]=-1;}

    for(int cur = 0; cur <N; cur++) {
        int l=0, r=N-1;
        int ans;
        while(l<r) {
            // set all switch to zero, and make it open
            for(int i=l; i<=r; i++) if(corDoor[i] == -1) corSet[i] = 0;
            ans = tryCombination(corSet);
            if(ans==-1 || ans>cur) {
                // door openned, 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];
            }

            // 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;
            } else {
                l=m+1;
            }
        }
        corDoor[l] = cur;
        corSet[l] = !corSet[l];

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

    }

    answer(corSet, corDoor);

}

/*
int main() {
    debug = true;
    ios_base::sync_with_stdio(false); cin.tie(0);

    exploreCave(5);

    if(debug) cout << endl << "EOL" << endl;

}
*/

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