Submission #1039382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039382		DeathIsAwe	Cave (IOI13_cave)	C++14	100 / 100	163 ms	816 KiB

cave

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


void exploreCave(int n) {
    int top, bottom, middle, result, locans;
    int ansvec[n], test[n], matching[n];
    bool sus, solved[n];
    for (int i=0;i<n;i++) {
        solved[i] = false;
    }



    for (int i=0;i<n;i++) {
        top = n-1; bottom = 0;
        for (int j=0;j<n;j++) {
            if (!solved[j]) {
                test[j] = 0;
            }
        }
        result = tryCombination(test);
        sus = true;
        if (result > i || result == -1) {
            sus = false;
        }
        locans = (int)sus;
        sus = true;
        while (bottom < top) {
            middle = (bottom + top) / 2;
            for (int j=bottom;j<=middle;j++) {
                if (!solved[j]) {
                    test[j] = (int)sus;
                }
            }
            //for (int j: test) {cout << j << ' ';}
            //cout << '\n';
            result = tryCombination(test);
            //cout << "b: " << bottom << "  t: " << top << "  m: " << middle << "  res: " << result;
            //cout << "  sus: " << sus;
            //cout << '\n';
            if (result == -1) {result = n;}
            if ((result > i  && (int)sus == locans) || (result == i && (int)sus != locans)) {
                top = middle;
                sus = !sus;
            } else {
                bottom = middle + 1;
            }
        }
        //cout << i << ' ' << top << ' ' << locans;
        //cout << '\n' << '\n';
        solved[top] = true;
        ansvec[top] = locans;
        test[top] = locans;
        matching[top] = i;
    }
    answer(ansvec, matching);
}

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