Submission #243928

#	Time	Username	Problem	Language	Result	Execution time	Memory
243928		Coroian_David	Cave (IOI13_cave)	C++11	100 / 100	502 ms	1144 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 ++)
    {
        if(v[i] == UNDEF)
        {
            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;

int ap[MAX_N + 1];

int APEL;

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";*//*
        ap[idx] ++;
        if(ap[idx] > 13)
            cout << " +12 " << ap[idx] << " " << idx << "\n";*/
        int x = tryCombination(q);
        APEL ++;
       /* ap[x] ++;
        if(ap[x] > 10)
            cout << "" << x << " PESTE 10 " << ap[x] << "\n";*/
     //   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 bagaRand()
{
    for(int i = 0; i < n; i ++)
    {
        q[i] = (v[i] == UNDEF ? rand() % 2 : v[i]);
    }
}

void exploreCave(int N)
{
    srand(time(0));

    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);
        APEL ++;
       /* ap[x] ++;
        if(ap[x] > 10)
            cout << "" << x << " PESTE 10 " << ap[x] << "\n";*/

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

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

        divide(0, N, x, 1);

//        bagaRand();
    }

    answer(v, id);
}

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