Submission #962656

#	Time	Username	Problem	Language	Result	Execution time	Memory
962656		danikoynov	Cave (IOI13_cave)	C++14	100 / 100	689 ms	868 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(b[i]);
          }

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

               ///cout << bit << endl;
          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(b[i]);
               }
               for (int i = mf + 1; i < N; i ++)
               {
                    if (!used[i])
                         comb.push_back(bit ^ 1);
                    else
                         comb.push_back(b[i]);
               }

               int ret = try_comb(comb);
               /**for (int i = 0; i < comb.size(); i ++)
                    cout << comb[i] << " ";
               cout << endl;
               cout << "ret " << ret << endl;*/
               if (ret != -1 && ret <= pos)
                    lf = mf + 1;
               else
                    rf = mf - 1;
          }

          used[lf] = 1;
          s[lf] = pos;
          b[lf] = bit;
          //cout << "found " << lf << " " << bit << " " << pos << endl;
     }
     /**for (int i = 0; i < N; i ++)
     {
          cout << b[i] << " ";
     }
     cout << endl;
     for (int i = 0; i < N; i ++)
     {
          cout << s[i] << " ";
     }
     cout << endl;*/
     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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24