Submission #716706

#	Time	Username	Problem	Language	Result	Execution time	Memory
716706		aykhn	Cave (IOI13_cave)	C++14	0 / 100	235 ms	372 KiB

cave

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

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)

#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) cout << v[i] << " "; cout<<endl;

void exploreCave(int N)
{
    int open[N];
    int ans[N];
    int used[N];

    for (int i = 0; i < N; i++)
    {
        open[i] = 0;
        used[i] = -1;
    }

    for (int i = 0; i < N; i++)
    {
        int l = 0;
        int r = N - 1;
        int pans = tryCombination(open);

        while (l < r)
        {
            int mid = (l + r) >> 1;

            for (int j = l; j <= mid; j++)
            {
                if (used[j] != -1) continue;

                open[j] = 1 - open[j];
            }
            int ans = tryCombination(open);
            for (int j = l; j <= mid; j++)
            {
                if (used[j] != -1) continue;

                open[j] = 1 - open[j];
            }

            if (pans == -1)
            {
                if (ans != i) l = mid + 1;
            }
            else if (pans == i)
            {
                if (ans != pans || ans == -1) r = mid;
                else l = mid + 1;
            }
            else
            {
                if (ans == i) r = mid;
                else l = mid + 1;
            }
        }
        used[l] = i;

        if (pans == i) open[l] = 1;
        else open[l] = 0;
    }

    answer(open, used);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:28:9: warning: unused variable 'ans' [-Wunused-variable]
   28 |     int ans[N];
      |         ^~~

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