Submission #154246

#	Time	Username	Problem	Language	Result	Execution time	Memory
154246		Ruxandra985	Cave (IOI13_cave)	C++14	100 / 100	290 ms	672 KiB

cave

#include <cstdio>
#include <iostream>
#define DIMN 5010
#include <vector>
#include "cave.h"

using namespace std;

void exploreCave(int n){
    int i,x,pos,st,dr,mid,j;
    int s[DIMN],d[DIMN];
    vector <int> v;
    for (i=0;i<n;i++)
        v.push_back(i); /// switch urile pe care nu le am fixat inca
    for (i=1;i<=n;i++){

        for (j=0;j<v.size();j++)
            s[v[j]] = 0;

        x = tryCombination (s);
        if (x == -1 || x >= i)
            pos = 0;
        else pos = 1;

        st = 0;
        dr = v.size()-1;
        while (st<dr){
            mid = (st + dr)/2;
            /// pui st..mid 0 si mid+1 dr 1
            for (j=st;j<=mid;j++)
                s[v[j]] = 0;
            for (j=mid+1;j<=dr;j++)
                s[v[j]] = 1;
            x = tryCombination(s);
            if (x >= i || x == -1){
                if (pos == 0)
                    dr = mid;
                else st = mid + 1;
            }
            else {
                if (pos == 1)
                    dr = mid;
                else st = mid + 1;
            }
        }
        //printf ("%d\n",v[st]);
        d[v[st]] = i-1;
        s[v[st]] = pos;
        swap(v[st] , v[v.size()-1]);
        v.pop_back();

    }
    answer (s,d);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<v.size();j++)
                  ~^~~~~~~~~

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