Submission #729898

#	Time	Username	Problem	Language	Result	Execution time	Memory
729898		Rasoul006	Cave (IOI13_cave)	C++17	0 / 100	2 ms	340 KiB

cave

#include "cave.h"

#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

#define all(x) x.begin() , x.end()

#define mid ((r+l)>>1)

#define lx (n<<1)

#define rx ((n<<1)|1)

typedef long long ll;

using namespace std;

const int N = 5e3+5;

const long long oo = 1e18 ;

int n , a[N] , b[N] , cur[N] ;

bool vis[N] , is ;

ll bs (ll l , ll r , ll x)
{
    if (l == r)
        return l ;

    for (int i = l ; i<=r ; i++)
    {
        if (vis[i]) continue ;
        cur[i] = !is ;
    }

    for (int i = l ; i<=mid ; i++)
    {
        if (vis[i]) continue ;
        cur[i] = is ;
    }

    bool p = (tryCombination(cur) == x) ;

    for (int i = l ; i<=mid ; i++)
    {
        if (vis[i]) continue ;
        cur[i] = !is ;
    }

    if (p)
        return bs(mid , r , x) ;
    else
        return bs(l , mid , x) ;
}

void exploreCave(int N) {

    n = N ;

    for (int i = 0 ; i<n ; i++)
    {
        for (int j = 0 ; j < n ; j++)
        {
            if (vis[j])
            {
                cur[j] = a[j] ;
                continue ;
            }

            a[j] = 0 ;
        }

        is = (tryCombination(a) == i) ;
        ll j = bs (0 , n-1 , i) ;
        a[j] = is ;
        b[j] = i ;
        vis[j] = true ;
    }

    answer (a , b) ;
}

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