Submission #876527

#	Time	Username	Problem	Language	Result	Execution time	Memory
876527		n3rm1n	Cave (IOI13_cave)	C++17	0 / 100	446 ms	600 KiB

cave

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

using namespace std;
const int MAXN = 5005;

 /* #define MAX_N 5000
  #define MAX_CALLS 70000

  #define fail(s, x   ) do { \
  		fprintf(stderr, s "\n", ## x); \
  		exit(1); \
  	} while(0)


  #define N koala
  #define realS kangaroo
  #define realD possum
  #define inv platypus
  #define num_calls echidna

  static int N;
  static int realS[MAX_N];
  static int realD[MAX_N];
  static int inv[MAX_N];
  static int num_calls;

  void answer(int S[], int D[]) {
      int i;
      int correct = 1;
      for (i = 0; i < N; ++i)
          if (S[i] != realS[i] || D[i] != realD[i]) {
              correct = 0;
              break;
          }

      if (correct)
          printf("CORRECT\n");
      else
          printf("INCORRECT\n");

      for (i = 0; i < N; ++i) {
          if (i > 0)
              printf(" ");
          printf("%d", S[i]);
      }
      printf("\n");

      for (i = 0; i < N; ++i) {
          if (i > 0)
              printf(" ");
          printf("%d", D[i]);
      }
      printf("\n");

      exit(0);
  }
  int n;
  int tryCombination(int S[]) {
      int i;

      if (num_calls >= MAX_CALLS) {
          printf("INCORRECT\nToo many calls to tryCombination() \n");
          exit(0);
      }
      for(int i = 0;i < n;++i){
      	cout << S[i] << ' ';
      }
      cout << '\n';
      ++num_calls;

      for (i = 0; i < N; ++i)
          if (S[inv[i]] != realS[inv[i]])
              return i;
      return -1;
  }

  /*int init() {
      int i, res;

      FILE *f = fopen("cave in", "r");
  	if (!f)
  		fail("Failed to open input file ");

  	res = fscanf(f, "%d", &N);

      for (i = 0; i < N; ++i) {
          res = fscanf(f, "%d", &realS[i]);
    }
     for (i = 0; i < N; ++i) {
         res = fscanf(f, "%d", &realD[i]);
        inv[realD[i]] = i;
    }

     num_calls = 0;
     return N;
 }*/


void exploreCave(int N)
{
    int n = N;
    int taken[n], crr[n], connected_to[n];
    memset(taken, 0, sizeof(taken));
     memset(crr, 0, sizeof(crr));
      memset(connected_to, 0, sizeof(connected_to));
    int curr_try[n];
    memset(curr_try, 0, sizeof(curr_try));
    for (int door = 0; door < n; ++ door)
    {
        if(tryCombination(crr) > door || tryCombination(crr) == -1)
        {
            int l = 0, r = n-1, mid, ans = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
                 for (int i = 0; i < mid; ++ i)
        curr_try[i] = 0;
    for (int i = mid; i < n; ++ i)
        curr_try[i] = 1;
    for (int i = 0; i < n; ++ i)
    {
        if(taken[i])curr_try[i] = crr[i];
    }

                int res = tryCombination(curr_try);
                if(res > door || res == -1)
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            taken[ans] = 1;
            crr[ans] = 0;
            connected_to[ans] = door;
        }
        else
        {
            int l = 0, r = n-1, mid, ans = -1;
            while(l <= r)
            {
                mid = (l + r)/2;
               for (int i = 0; i < mid; ++ i)
        curr_try[i] = 1;
    for (int i = mid; i < n; ++ i)
        curr_try[i] = 0;
    for (int i = 0; i < n; ++ i)
    {
        if(taken[i])curr_try[i] = crr[i];
    }
                int res = tryCombination(curr_try);
                if(res > door || res == -1)
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            taken[ans] = 1;
            crr[ans] = 1;
            connected_to[ans] = door;
        }
    }
    answer(crr, connected_to);
}
  /*int main()
  {
  	cin >> n;
  	for(int i = 0;i < n;++i){
  		cin >> realS[i];
  	}
  	for(int i = 0;i < n;++i){
  		cin >> realD[i];
  	}
  	exploreCave(n);
  }*/
/***
4
1 1 0 0
3 1 2 0
98
0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 1
4 83 15 55 57 96 5 36 35 44 34 22 10 47 9 90 88 17 63 37 42 51 6 86 25 79 70 85 19 92 69 38 84 18 41 43 31 46 49 67 82 8 91 28 77 66 97 39 89 68 64 45 40 93 75 13 73 54 24 0 14 29 71 80 81 1 33 16 61 26 20 72 87 60 30 3 23 78 59 27 52 53 12 76 62 56 7 95 32 21 65 2 74 48 94 58 50 11

*/

Compilation message (stderr)

cave.cpp:78:3: warning: "/*" within comment [-Wcomment]
   78 |   /*int init() {
      |

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