Submission #1072906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072906		That_Salamander	Minerals (JOI19_minerals)	C++17	100 / 100	977 ms	3844 KiB

minerals

#include <bits/stdc++.h>

void Solve(int N);
int Query(int x);

void Answer(int x, int y);

bool inMachine[100005];
int lastRes = 0;

int opCount = 0;
void setInMachine(int i, bool val) {
    if (inMachine[i] != val) {
        lastRes = Query(i);
        opCount++;
        inMachine[i] = val;
    }
}

void flip(int i) {
    setInMachine(i, !inMachine[i]);
}

int query() {
    return lastRes;
}

std::mt19937 shuffler(0);

int numQueries[43001];
int splitPoints[43001];

void setup() {
  if (numQueries[1] != 0) return;
  numQueries[0] = 0;
  numQueries[1] = 1;
  for (int i = 2; i <= 43000; i++) {
        int best = 1000000000;
        for (int splitPoint = 1; splitPoint < i; splitPoint++) {
            int ops = numQueries[splitPoint] + numQueries[i - splitPoint] + splitPoint + i;
            if (ops < best) {
                best = ops;
                splitPoints[i] = splitPoint;
            }
        }
        numQueries[i] = best;
    }
}

void findMatching(std::vector<int>& a, std::vector<int>& b, bool aIsSet) {
  setup();
    if (a.size() == 0) 
        exit(1);
    if (a.size() == 1) {
        Answer(a[0], b[0]);
        return;
    }

    std::shuffle(a.begin(), a.end(), shuffler);
    std::shuffle(b.begin(), b.end(), shuffler);

    std::vector<int> a1, a2, b1, b2;

    int bound;
    if (aIsSet) {
        bound = splitPoints[a.size()];
    } else {
        bound = a.size() - splitPoints[a.size()];
    }

    if (bound == 0) bound++;
    if (bound == a.size()) bound--;

    for (int i = 0; i < a.size(); i++) {
        if (i < bound) {
            a1.push_back(a[i]);
        } else {
            a2.push_back(a[i]);
        }
    }

    //std::cout << a1.size() << " " << a2.size() << std::endl;
    
    //std::cout << a1.size() << " " << a2.size() << std::endl;

    for (int x: a1) {
        setInMachine(x, false);
    }

    for (int x: a2) {
        setInMachine(x, true);
    }

    for (int x: b) {
        if (a1.size() == b1.size()) b2.push_back(x);
        else if (a2.size() == b2.size()) b1.push_back(x);
        else {
            int prev = query();
            flip(x);
            if (prev != query()) {
                b1.push_back(x);
            } else {
                b2.push_back(x);
            }
        }
    }

    //std::cout << a1.size() << " " << b1.size() << std::endl;

    findMatching(a1, b1, false);
    findMatching(a2, b2, true);
}

void Solve(int N) {
    lastRes = 0;
    opCount = 0;
    memset(inMachine, 0, sizeof(inMachine));

    std::vector<int> a, b;

    for (int i = 1; i <= 2 * N; i++) {
        int prev = query();
        flip(i);
        if (prev == query()) {
            b.push_back(i);
        } else {
            a.push_back(i);
        }
    }

    findMatching(a, b, true);
}

#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
#include <algorithm>

constexpr int MAX_N = 43000;
constexpr int MAX_CALLS = 1000000;

namespace {

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}

int N;
int counterpart[2 * MAX_N + 1];

int num_queries;
int num_kinds;
int on[2 * MAX_N + 1];
int count[2 * MAX_N + 1];

int num_answers;
int answer[2 * MAX_N + 1];

}  // namespace

int Query(int x) {
  if (!(1 <= x && x <= 2 * N)) {
    printf("Query(%d)\n", x);
    WrongAnswer(1);
  }
  if (++num_queries > MAX_CALLS) {
    //WrongAnswer(2);
  }
  const int type = std::min(x, counterpart[x]);
  if (on[x]) {
    --on[x];
    --count[type];
    if (count[type] == 0) {
      --num_kinds;
    }
  } else {
    ++on[x];
    ++count[type];
    if (count[type] == 1) {
      ++num_kinds;
    }
  }
  return num_kinds;
}

void Answer(int a, int b) {
  if (N < 100)
    std::cout << "Answer(" << a << ", " << b << ")" << std::endl;
  if (++num_answers > N) {
    WrongAnswer(6);
  }
  if (!(1 <= a && a <= 2 * N && 1 <= b && b <= 2 * N)) {
    WrongAnswer(3);
  }
  if (answer[a] != 0) {
    WrongAnswer(4);
  }
  answer[a] = b;
  if (answer[b] != 0) {
    WrongAnswer(4);
  }
  answer[b] = a;
  if (!(counterpart[a] == b && counterpart[b] == a)) {
    WrongAnswer(5);
  }
}

int secret_order[100000];

int main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }

  for (int i = 0; i < 2 * N; ++i) {
    secret_order[i] = i + 1;
  }

  std::random_device rd;
  std::mt19937 rng(rd());
 
  int maxQueries = 0;
  for (int iter = 0; iter < 100; iter++) {
    num_queries = 0;
    num_kinds = 0;
    memset(on, 0, sizeof(on));
    memset(count, 0, sizeof(count));
    num_answers = 0;
    memset(answer, 0, sizeof(answer));
    memset(counterpart, 0, sizeof(counterpart));
    std::shuffle(secret_order, secret_order + 2 * N, rng);

    for (int i = 1; i <= N; ++i) {
        int x, y;
        x = secret_order[2 * i - 2];
        y = secret_order[2 * i - 1];
        /*if (scanf("%d%d", &x, &y) != 2) {
        fprintf(stderr, "Error while reading input\n");
        exit(1);
        }*/
    if (N < 100)
    printf("%d %d\n", x, y);
        counterpart[x] = y;
        counterpart[y] = x;
    }
    Solve(N);
    if (num_answers != N) {
        WrongAnswer(6);
    }
    printf("Accepted: %d\n", num_queries);
    maxQueries = std::max(maxQueries, num_queries);
  }
  std::cout << "Max queries: " << maxQueries << std::endl;
  return 0;
}
#endif

Compilation message (stderr)

minerals.cpp: In function 'void findMatching(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     if (bound == a.size()) bound--;
      |         ~~~~~~^~~~~~~~~~~
minerals.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10