Submission #578829

#	Time	Username	Problem	Language	Result	Execution time	Memory
578829		Mazaalai	Cave (IOI13_cave)	C++17	64 / 100	397 ms	460 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int n;
// tryCombination
void exploreCave(int N) {
    n = N;
    int lastAns = 0;
    int value[n], switches[n]; memset(value, 0, sizeof(value));
    bool assigned[N]; memset(assigned, 0, sizeof(assigned));
    int assignCnt = 0;
    bool done = 0;
    for (int i = 0; i < n && !done; i++) {
        int nums[n], tar = 0;
        for (int j = 0; j < n; j++) {
            nums[j] = 0;
            if (assigned[j]) nums[j] = value[j];
        }
        int cur = tryCombination(nums);
        if (cur == -1) {
            for (int j = 0; j < n; j++) value[j] = nums[j];
            break;
        } else if(assignCnt==n-1 && cur == n-1) {
            // cout << "HERE?\n";
            for (int j = 0; j < n; j++) {
                nums[j] = 1;
                if (assigned[j]) nums[j] = value[j];
            }
            for (int j = 0; j < n; j++) value[j] = nums[j];
            break;
        }
        if (cur == i) tar = 1; // did not open
        int l = 0, r = n-1, res = r;
        while(l <= r && !done) {
            // checkLeft
            int mid = (l+r)>>1;
            int L = l, R = mid;
            for (int j = 0; j < n; j++) {
                if (assigned[j]) nums[j] = value[j];
                else {
                    if (L <= j && j <= R) {
                        nums[j] = tar;
                    } else {
                        nums[j] = tar^1;
                    }
                }
            }
            cur = tryCombination(nums);
            if (cur == -1) {
                for (int j = 0; j < n; j++) 
                    value[j] = nums[j];
                
                done = 1;
                break;
            }
            if (cur == i) { // did not open
                l = mid+1;
            } else {
                r = mid;
            }
            if (l == r) {
                res = l;
                break;
            }
        }
        if (!done) {
            assigned[res] = 1; assignCnt++;
            value[res] = tar;
        }
    }
    // for (int i = 0; i < n; i++) cout << value[i] << " \n"[i==n-1];
    for (int i = 0; i < n; i++) {
        value[i] ^= 1;
        switches[i] = tryCombination(value);
        value[i] ^= 1;
    }
    answer(value, switches);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:8:9: warning: unused variable 'lastAns' [-Wunused-variable]
    8 |     int lastAns = 0;
      |         ^~~~~~~

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