Submission #687362

#	Time	Username	Problem	Language	Result	Execution time	Memory
687362		Bliznetc	Cave (IOI13_cave)	C++17	0 / 100	40 ms	392 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second

typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vi >  vvi;


void exploreCave (int n) {
    int ask[n];
    int good[n];
    int d[n];
    for (int i = 0; i < n; i++) {
        good[i] = d[i] = -1;
    }
//    vector<int> good(n, -1), d(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (good[j] != -1) {
                ask[j] = 0;
            }
            else {
                ask[j] = good[j];
            }
        }

        int x = tryCombination(ask);
        if (x == i) {
            for (int j = 0; j < n; j++) {
                if (good[j] != -1) {
                    ask[j] = 1;
                }
                else {
                    ask[j] = good[j];
                }
            }
        }

        int l = 0, r = n - 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            for (int j = l; j < mid; j++) {
                if (good[j] != -1) {
                    ask[j] = 1 - ask[j];
                }
                else {
                    ask[j] = good[j];
                }
            }

            x = tryCombination(ask);
            if (x == i) {
                for (int j = l; j < mid; j++) {
                    if (good[j] != -1) {
                        ask[j] = 1 - ask[j];
                    }
                    else {
                        ask[j] = good[j];
                    }
                }
                for (int j = mid; j <= r; j++) {
                    if (good[j] != -1) {
                        ask[j] = 1 - ask[j];
                    }
                    else {
                        ask[j] = good[j];
                    }
                }
                r = mid - 1;
            }
            else {
                l = mid;
            }
        }


        /*f (good[l] != -1) {
            ask[l] = 1 - ask[l];
        }
        else {
            ask[l] = good[l];
        }
        x = tryCombination(ask);
        if (x == i) {
            if (good[l] != -1) {
                ask[l] = 1 - ask[l];
            }
            else {
                ask[l] = good[l];
            }
            l = r;
        }*/

        good[i] = ask[l];
        d[i] = l;
    }

    answer(good, d);
}

/*
signed main() {
    vi a;
    a.pb(-2);
    a.pb(2);
    a.pb(2);
    a.pb(-2);
    a.pb(-2);
    a.pb(2);
    cout << count_swaps(a);
}
 */

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