Submission #962668

#	Time	Username	Problem	Language	Result	Execution time	Memory
962668		Ice_man	Cave (IOI13_cave)	C++14	100 / 100	337 ms	680 KiB

cave

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include "cave.h"
#include <map>
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cstdio>

#define maxn 5005
#define maxn2 205
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}*/

typedef pair <int, int> pii;

int a , b , t;
int w[maxn] , s[maxn];

int x[maxn] , y[maxn];
pii pom[maxn];

int used[maxn];
int n;


int up[maxn];


void help(int m)
{
    for(; m > -1; m--)
        if(used[m] == -1)
            up[m] = !up[m];
}




void exploreCave(int N)
{
    n = N;
    for(int i = 0; i < n; i++)
    {
        used[i] = -1;
        up[i] = 0;
    }

    int l , r , mid;
    int cur_ans;

    for(int i = 0; i < n; i++)
    {
        if(tryCombination(up) == i)
            help(N);
        l = 0;
        r = n - 1;
        cur_ans = -1;


        while(l <= r)
        {
            mid = (l + r) / 2;
            help(mid);
            int save = tryCombination(up);
            help(mid);
            if(save == i)
            {
                r = mid - 1;
                cur_ans = mid;
            }
            else l = mid + 1;
        }

        used[cur_ans] = i;
    }


    answer(up , used);
}



/**int main()
{

    #ifdef ONLINE_JUDGE /// promeni
        freopen("input.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //startT = std::chrono::high_resolution_clock::now();





    return 0;
}*/

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