Submission #583578

#	Time	Username	Problem	Language	Result	Execution time	Memory
583578		kirill_iceland	Cave (IOI13_cave)	C++14	0 / 100	79 ms	65536 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(__typeof(a) i = a; a < b; i++)
typedef pair<int, int> ii;
typedef vector<int> vi;

void exploreCave(int n){
    srand(2801043610);
    int swiches[n];
    memset(swiches, 0, sizeof(swiches));
    vi swiches2;
    int connections[n]; // swich --> door
    memset(connections, -1, sizeof(connections));

    rep(i, 0, n){
        swiches2.push_back(i);
    }

    int pr = rand() % swiches2.size();
    int pswich = swiches2[pr];
    swiches[pswich] = 1 - swiches[pswich];
    int pres = tryCombination(swiches);
    while(true){
        int r = rand() % swiches2.size();
        int swich = swiches2[r];
        swiches[swich] = 1 - swiches[swich];
        int res = tryCombination(swiches);
        if(pres == -1){
            connections[swich] = res;
            swiches[swich] = 1 - swiches[swich]; //open door
            swiches2.erase(swiches2.begin() + r);
            res = pres;
            if(r > pr){
                r = pr;
            }else{
                r = pr - 1;
            }
        }else if(res == -1){
            connections[swich] = pres;
            swiches2.erase(swiches2.begin() + pr);
        }else if(pres < res){ //door opened
            connections[swich] = pres;
            swiches2.erase(swiches2.begin() + pr);
        }else if(pres > res){ //door closed
            connections[swich] = res;
            swiches[swich] = 1 - swiches[swich]; //open door
            swiches2.erase(swiches2.begin() + r);
            res = pres; 
            if(r > pr){
                r = pr;
            }else{
                r = pr - 1;
            }
        }
        
        if(swiches2.size() == 0){
            answer(swiches, connections);
            return;
        }
        pswich = swich;
        pr = r;
    }
}

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