Submission #796848

#	Time	Username	Problem	Language	Result	Execution time	Memory
796848		Mohammed_Atalah	Cave (IOI13_cave)	C++17	100 / 100	511 ms	688 KiB

cave

#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
int can_change [5000];
int S [5000]; // correct position
int D [5000]; // destination

// tryCombination() => to check

int n;
int nums [5000];
void solve_for_X(int x) {

    int e = tryCombination(nums);

    if (e != x) {
        for (int i = 0; i < n ; i ++) {
            if (!can_change[i]) {
                if (nums[i] == 1) {
                    nums[i] = 0;
                } else {
                    nums[i] = 1;
                }
            }
        }
    }

    int l = 0;
    int r = n - 1;

    int  v[5000] =  {1};
    while (l < r) {
        // if (x == 3) {
        //     cout << l << " " << r << endl;
        // }
        // v = nums;
        // if (x == 3) {
        //     cout << v[0] << " " << v[1] << endl;
        // }
        int mid = (l + r) / 2;
        for (int i = 0; i < n; i++) {
            if (l <= i && i <= mid && !can_change[i]) {
                if (nums[i] == 1) {
                    v[i] = 0;
                } else {
                    v[i] = 1;
                }
            } else {
                v[i] = nums[i];
            }
        }
        // if (x == 3) {
        //     cout << v[0] << " " << v[1] << endl;
        // }
        e = tryCombination(v);
        if (e > x ||  e == -1) {
            r = mid;
        } else {
            l = mid + 1;
        }

    }

    can_change[l] = 1;
    // cout << x << " " << l << endl;
    if (nums[l] == 1) {
        S[l] =  0;
        nums[l] =  0;
    } else {
        S[l] =  1;
        nums[l] =  1;
    }
    D[l] = x;

}



void exploreCave(int N) {
    n = N;


    for (int i = 0; i < N ; i++) {
        nums[i] = 1;
    }
    for (int i = 0; i < N ; i++) {
        solve_for_X(i);
    }

    answer(S, D);
}

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