| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1215362 | AbdullahIshfaq | Minerals (JOI19_minerals) | C++20 | 0 ms | 0 KiB |
// code written by gpt
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
// We'll perform a parallel binary search over 2N positions.
// Each position i has a target type (0 or 1). We maintain for each i a search interval [lo[i], hi[i]].
// In each round, we group all i whose lo[i] < hi[i] by mid = (lo+hi)/2, query all mids in one batch,
// then update lo or hi based on whether Query(mid) distinguishes their target change.
int main() {
int N = GetLength(); // Provided by minerals.h: returns N
int total = 2 * N;
// Each index [1..2N] has search range [1..2N]
vector<int> lo(total + 1, 1), hi(total + 1, total);
vector<int> last_query(total + 1, -1);
// While there is some index with lo < hi
bool changed = true;
while (changed) {
changed = false;
// Map from mid -> list of indices
unordered_map<int, vector<int>> bucket;
for (int i = 1; i <= total; i++) {
if (lo[i] < hi[i]) {
int mid = lo[i] + (hi[i] - lo[i]) / 2;
bucket[mid].push_back(i);
changed = true;
}
}
// For each unique mid, perform one Query(mid) call
for (auto &p : bucket) {
int mid = p.first;
bool response = Query(mid);
// For each index needing this mid, update its interval
for (int idx : p.second) {
// If Query(mid) changed from last_query[idx], target is <= mid
if (last_query[idx] == -1) {
// First time, just record
last_query[idx] = response;
// Keep interval unchanged this round
} else {
if (response == last_query[idx]) {
// same as before: element <= mid
hi[idx] = mid;
} else {
// changed: element > mid
lo[idx] = mid + 1;
last_query[idx] = response;
}
}
}
}
}
// Once lo[i] == hi[i], we know the exact type boundary for i
for (int i = 1; i <= total; i++) {
Answer(i, lo[i]);
}
return 0;
}