Submission #787644

#	Time	Username	Problem	Language	Result	Execution time	Memory
787644		That_Salamander	Cave (IOI13_cave)	C++17	Compilation error	0 ms	0 KiB

cave

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <cstring>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <cassert>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int tryCombination(int S[]);
void answer(int S[], int D[]);

void exploreCave(int n) {
    vector<int> zero(n);

    vector<pair<int, int>> known;
    set<int> unknown;

    FOR(i, n) {
        unknown.insert(i);
    }

    FOR(i, n) {
        int res = tryCombination(zero.data());
        bool openOnZero = res == -1 || res >= i + 1;

        vector<int> currTest(n, !openOnZero);

        for (auto p: known) {
            currTest[p.first] = p.second;
        }

        vector<int> frontier(unknown.begin(), unknown.end());

        int l = 0;
        int r = frontier.size() - 1;

        while (r > l) {
            int m = (l + r) / 2;

            for (int j = l; j <= m; j++) {
                currTest[frontier[j]] = openOnZero;
            }

            bool didClose = tryCombination(currTest.data()) == i;

            for (int j = l; j <= m; j++) {
                currTest[frontier[j]] = !openOnZero;
            }

            if (didClose) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        int d = frontier[l];

        unknown.erase(d);
        zero[d] = !openOnZero;
        known.push_back({d, !openOnZero});

        //cout << "Door " << i << " is opened by switch " << d << " which is set to " << !openOnZero << endl;
    }

    vector<int> d(n);

    FOR(i, n) {
        d[known[i].first] = i;
    }

    answer(zero.data(), d.data());
}

#ifdef LOCAL_TEST
#define MAX_N 5000
#define MAX_CALLS 70000

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;
  for (i = 0; i < N; ++i)
    if (S[i] != realS[i] || D[i] != realD[i]) {
      printf("INCORRECT\nWrong answer:");
      if (S[i] != realS[i])
        printf("S[%d] != realS[%d]\n", i, i);
      else
        printf("D[%d] != realD[%d]\n", i, i);
      exit(0);
    }

  printf("CORRECT\n");
}

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;

  assert(scanf("%d", &N) == 1);

  for (i = 0; i < N; ++i) {
    assert(scanf("%d", &realS[i]) == 1);
  }
  for (i = 0; i < N; ++i) {
    assert(scanf("%d", &realD[i]) == 1);
    inv[realD[i]] = i;
  }

  num_calls = 0;
  return N;*/

  N = 5000;
  FOR(i, N) {
    realS[i] = rand() % 2;
  }

  vector<int> d(N);
    FOR(i, N) {
        d[i] = i;
    }

    random_device rd;
    mt19937 g(rd());

    shuffle(d.begin(), d.end(), g);

    FOR(i, N) {
        realD[d[i]] = i;
        inv[i] = d[i];
    }

    num_calls = 0;

    /*cout << "N = " << N << endl;
    FOR(i, N) {
        cout << realS[i] << " ";
    }
    cout << endl;
    FOR(i, N) {
        cout << realD[i] << " ";
    }
    cout << endl;*/

    return N;
}

int main() {
    FOR(i, 100) {
        int N;
        N = init();
        exploreCave(N);

        cout << "Done in " << num_calls << " calls!" << endl;
    }
}
#endif

Compilation message (stderr)

/usr/bin/ld: /tmp/ccxYUEfS.o: in function `exploreCave(int)':
cave.cpp:(.text+0x39e): undefined reference to `tryCombination(int*)'
/usr/bin/ld: cave.cpp:(.text+0x550): undefined reference to `tryCombination(int*)'
/usr/bin/ld: cave.cpp:(.text+0x762): undefined reference to `answer(int*, int*)'
/usr/bin/ld: /tmp/cc84FJXS.o: in function `main':
grader.c:(.text.startup+0x10): undefined reference to `exploreCave'
collect2: error: ld returned 1 exit status