Submission #482659

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

/*
int tryCombination(int S[]){
    int s0[] ={1,1,1,0}, d0[] = {3,1,0,2};
    int ok[] ={0,0,0,0};
    for(int i=0;i<4;i++) {
        if(S[i]==s0[i]) ok[d0[i]] = 1;
    }
    for(int i=0;i<4;i++)
        if(!ok[i]) return i;
    return -1;
}
void answer(int s[], int d[]) {
    cout << "final answer" << endl;
    printKey(s,d,4);
}
*/
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];

    if(N==1) {
        corDoor[0] = 0;
        corSet[0] = 1;
        if(tryCombination(corSet)==0) corSet[0] = 0;
        answer(corSet, corDoor);
    }


    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 = 1;
        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 << "temp answer -- " << endl;
            printKey(corSet, corDoor, N);
        }

    }

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

}

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

    exploreCave(4);

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

}
*/

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