Submission #962651

#	Time	Username	Problem	Language	Result	Execution time	Memory
962651		danikoynov	Cave (IOI13_cave)	C++14	0 / 100	325 ms	600 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 5010;

int used[maxn], s[maxn], d[maxn], b[maxn];
int arr[maxn];

int try_comb(vector < int > v)
{
     for (int i = 0; i < v.size(); i ++)
          arr[i] = v[i];
     return tryCombination(arr);
}
void exploreCave(int N)
{

     for (int pos = 0; pos < N; pos ++)
     {
          vector < int > comb;
          int bit = 0;
          for (int i = 0; i < N; i ++)
          {
               if (!used[i])
                    comb.push_back(bit);
               else
                    comb.push_back(s[i]);
          }

          int door = try_comb(comb);
          if (door != -1 && door <= pos)
               bit ^= 1;

          comb.clear();
          int lf = 0, rf = N - 1;
          while(lf <= rf)
          {
               int mf = (lf + rf) / 2;
               comb.clear();
               for (int i = 0; i <= mf; i ++)
               {
                    if (!used[i])
                         comb.push_back(bit);
                    else
                         comb.push_back(s[i]);
               }
               for (int i = mf + 1; i < N; i ++)
               {
                    if (!used[i])
                         comb.push_back(bit ^ 1);
                    else
                         comb.push_back(s[i]);
               }

               int ret = try_comb(comb);
               if (ret != -1 && ret <= pos)
                    lf = mf + 1;
               else
                    rf = mf - 1;
          }

          used[rf] = 1;
          s[rf] = pos;
          b[rf] = bit;
     }

     answer(b, s);
}

Compilation message (stderr)

cave.cpp: In function 'int try_comb(std::vector<int>)':
cave.cpp:14:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |      for (int i = 0; i < v.size(); i ++)
      |                      ~~^~~~~~~~~~

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