Submission #950384

#	Time	Username	Problem	Language	Result	Execution time	Memory
950384		kilkuwu	Cave (IOI13_cave)	C++11	100 / 100	258 ms	820 KiB

cave

#ifdef LOCAL
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
#else 
#include "cave.h"
#endif

#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

#include <bits/stdc++.h>

constexpr int mxN = 5000;
int s[mxN], d[mxN], ord[mxN];
int _n;

int ask_switched(int p) {
  for (int i = p; i < _n; i++) {
    s[ord[i]] ^= 1;
  }
  int res = tryCombination(s); 
  for (int i = p; i < _n; i++) {
    s[ord[i]] ^= 1;
  }
  if (res == -1) res = _n;
  return res;
}

/*

opened = 0 
2
0 0 
1 0 

 */

void exploreCave(int N) {
  _n = N;
  for (int i = 0; i < N; i++) ord[i] = i;
  for (int i = 0; i < N; i++) {
    int opened = tryCombination(s);
    if (opened == -1) opened = N;
    int is_open = opened > i; // opened >= i anyway
    if (is_open) {
      // find first switch to make it close
      int lb = i, rb = N - 1;
      while (lb < rb) {
        int mid = (lb + rb + 1) / 2;

        if (ask_switched(mid) <= i) {
          lb = mid;
        } else {
          rb = mid - 1;
        }
      }

      d[ord[lb]] = i;
      std::swap(ord[lb], ord[i]);
    } else {
      int lb = i, rb = N - 1;
      while (lb < rb) {
        int mid = (lb + rb + 1) / 2;

        if (ask_switched(mid) > i) {
          lb = mid;
        } else {
          rb = mid - 1;
        }
      }

      d[ord[lb]] = i;
      std::swap(ord[lb], ord[i]);
      
      // we gotta swap this 

      s[ord[i]] ^= 1;
    }
  }

  answer(s, d);
}

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 5000
#define MAX_CALLS 70000

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

/* Symbol obfuscation */
#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 tryCombination(int S[]) {
  int i;

  if (num_calls >= MAX_CALLS) {
    printf("INCORRECT\nToo many calls to tryCombination().\n");
    exit(0);
  }
  ++num_calls;

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

int init() {
  int i;

  std::cin >> N;

  for (i = 0; i < N; ++i) {
    std::cin >> realS[i];
  }
  for (i = 0; i < N; ++i) {
    std::cin >> realD[i];
    inv[realD[i]] = i;
  }

  num_calls = 0;
  return N;
}

int main() {
  int n;
  n = init();
  exploreCave(n);
  printf("incorrect\nyour solution did not call answer().\n");
  return 0;
}
#endif

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