Submission #243919

#	Time	Username	Problem	Language	Result	Execution time	Memory
243919		Coroian_David	Cave (IOI13_cave)	C++11	64 / 100	490 ms	888 KiB

cave

#include <bits/stdc++.h>

#include "cave.h"

#define MAX_N 5000

using namespace std;

int tryCombination(int S[]);
void answer(int S[], int D[]);

int id[MAX_N + 1];
int v[MAX_N + 1];

const int UNDEF = -1;

int q[MAX_N + 1];

void baga(int st, int dr, int val)
{
    for(int i = st; i <= dr; i ++)
    {
        //cout << " BAGAM " << i << " " << val << "\n";
        //cout << " AVEM " << v[i] << " == " << UNDEF << " " << (v[i] == UNDEF) << "\n";

        q[i] = (v[i] == UNDEF ? val : v[i]);
    }
}


int tmp[MAX_N + 1];

int n;

void copyV(int a[], int b[])
{
    for(int i = 0; i < n; i ++)
        a[i] = b[i];
}

void doSpec()
{
    for(int i = 0; i < n; i ++)
    {
        q[i] = 1 - q[i];

        int x = tryCombination(q);
        id[i] = x;
        v[i] = 1 - q[i];

        q[i] = 1 - q[i];
    }

    answer(v, id);
}

int done[MAX_N + 1];

int CATE = 0;

void divide(int st, int dr, int idx, int val)
{
  //  cout << " INTRA " << st << " " << dr << " " << idx << " " << val << "\n";

    if(st == dr)
    {

//        cout << " PE POZ " << st << " ARE VAL " << val << " SI ID " << idx << "\n";

        id[st] = idx;
        v[st] = val;
        q[st] = val;
        done[idx] = 1;
        CATE ++;

        return;
    }

   /* cout << idx << " ESTE " << done[idx] << "\n";
    for(int i = 0; i < n; i ++)
        cout << v[i] << " ";
    cout << "\n";
    for(int i =0 ; i < n; i++)
        cout << id[i] << " ";
    cout << "\n";*/

    int tmp[MAX_N + 1];
    int mid = (st + dr) >> 1;
    while(done[idx] == 0)
    {/*
        cout << " SUNITEM " << st << " " << dr << " " << idx << " " << val << "\n";
        for(int i =0; i <= 5; i ++)
            cout << q[i ] << " " ;
        cout << "\n";*/
        copyV(tmp, q);
        baga(st, mid, val);
/*
        for(int i =0; i <= 5; i ++)
            cout << q[i ] << " " ;
        cout << "\n";*/
        int x = tryCombination(q);
     //   cout << "PR ++ " << x << "\n";


   /* for(int i =0 ; i < n; i++)
        cout << q[i] << " ";
    cout << "\n";*/

        if(x == -1)
            doSpec();

        if(x < idx)
        {
            divide(st, mid, x, 1 - val);
                copyV(q, tmp);
        }

        else
            if(x == idx)
            {
                divide(mid + 1, dr, idx, val);
                copyV(q, tmp);
            }

        else
            if(x > idx)
            {
                copyV(q, tmp);
                divide(st, mid, idx, val);
            }
    }
}

void exploreCave(int N)
{
    n = N;
    for(int i = 0; i < N; i ++)
    {
        v[i] = UNDEF;
        id[i] = UNDEF;
        q[i] = 0;
    }

    while(CATE < N)
    {
        baga(0, N, 0);
        int x = tryCombination(q);

  //      cout << " PRIMA E " << x << " " << "\n";

        if(x == -1)
            doSpec();

        divide(0, N, x, 1);
    }

    answer(v, id);
}

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