Submission #556134

#	Time	Username	Problem	Language	Result	Execution time	Memory
556134		ljuba	Cave (IOI13_cave)	C++17	100 / 100	1256 ms	468 KiB

cave

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

int n;

using namespace std;

void exploreCave(int N) {
    /* ... */
    n = N;

    int okidac[n];
    int gde[n]; //okidac na itom mestu pokazuje na vrata gde[i]
    bool marked[n];

    for(int i = 0; i < n; ++i) {
        marked[i] = false;
        gde[i] = 3*n;
    }

    for(int iter = 0; iter < n; ++iter) {
        int trenutni[n];

        for(int i = 0; i < n; ++i) {
            trenutni[i] = 0;
        }

        for(int i = 0; i < n; ++i) {
            if(gde[i] < iter) {
                trenutni[i] = okidac[i];
            }
        }

        int odg = tryCombination(trenutni);

        int x;

        if(odg == -1 || odg > iter) {
            x = 0;
        } else {
            x = 1;
        }

        int l = 1, r = n - iter;
        int zapravoGde = -1;
        int ans = -1;

        while(l <= r) {
            int mid = (l + r) / 2;

            for(int i = 0; i < n; ++i) {
                trenutni[i] = x ^ 1;
            }

            for(int i = 0; i < n; ++i) {
                if(gde[i] < iter) {
                    trenutni[i] = okidac[i];
                }
            }

            int uzeli = 0;
            for(int i = 0; i < n; ++i) {
                if(marked[i]) continue;
                ++uzeli;
                trenutni[i] = x;
                if(uzeli == mid) {
                    zapravoGde = i;
                    break;
                }
            }

            // if(l == r) break;

            odg = tryCombination(trenutni);

            // cerr << l << " " << r << " ";
            // cerr << "(" << iter << ", " << mid << "):";
            // for(int i = 0; i < n; ++i) cerr << " " << trenutni[i];
            // cerr << " -> " << odg << endl;

            if(odg == -1 || odg > iter) {
                ans = zapravoGde;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        gde[ans] = iter;
        okidac[ans] = x;
        marked[ans] = true;
    }

    answer(okidac, gde);
}

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