Submission #1071823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071823		That_Salamander	Minerals (JOI19_minerals)	C++14	0 / 100	2 ms	600 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;
    }
}

int query() {
    return lastRes;
}

int ans[50000];
int maxAns[50000];

std::vector<int> a, b;

void Solve(int N) {
    std::vector<int> order(2 * N);
    std::iota(order.begin(), order.end(), 1);
    std::mt19937 rng(time(NULL));
    std::shuffle(order.begin(), order.end(), rng);

    for (int i = 1; i <= 2 * N; i++) {
        int prev = query();
        setInMachine(i, true);
        if (prev != query()) {
            a.push_back(i);
        } else {
            maxAns[b.size()] = a.size() - 1;
            b.push_back(i);
        }
    }

    std::vector<bool> fixed(N);

    int numSaved = 0;

    int m = 1;

    while (m < N) {
        std::unordered_map<int, int> ansCounts;
        for (int i = 0; i < N; i++) ansCounts[ans[i]]++;

        std::unordered_map<int, int> numIncr, numSame;
        std::unordered_set<int> fixed, fixedB;

        for (int i = 0; i < N; i++) {
            if (ans[i] + m > maxAns[i] || ansCounts[ans[i]] == 1) {
                fixed.insert(ans[i]);
                fixedB.insert(i);
                numSame[ans[i]]++;

                if (ansCounts[ans[i]] == 1) numSaved++;
            }
        }

        std::vector<int> order(N);
        std::iota(order.begin(), order.end(), 0);
        std::shuffle(order.begin(), order.end(), rng);

        std::vector<int> aSplitOne, aSplitTwo;

        for (int i = 0; i < N; i++) {
            if (fixed.find(i) == fixed.end()) {
                if (i & m) {
                    aSplitTwo.push_back(i);
                } else {
                    aSplitOne.push_back(i);
                }
            }
        }

        int costNormal = 0;
        int costReverse = 0;

        for (int x: aSplitOne) {
            if (inMachine[a[x]]) {
                costNormal++;
            } else {
                costReverse++;
            }
        }

        for (int x: aSplitTwo) {
            if (inMachine[a[x]]) {
                costReverse++;
            } else {
                costNormal++;
            }
        }

        /*std::cout << aSplitOne.size() << " " << aSplitTwo.size() << std::endl;
        std::cout << costNormal << " " << costReverse << std::endl;
        if (costNormal > costReverse) {
            std::cout << "Losing " << costNormal - costReverse << " operations" << std::endl;
        }*/

       bool invert = costNormal > costReverse;

        int numSet = 0;
        std::vector<int> numSets;
        opCount = 0;
        for (int i = 0; i < N; i++) {
            if (fixed.find(i) == fixed.end()) {
                if (invert) {
                    setInMachine(a[i], !(i & m));
                } else {
                    setInMachine(a[i], (i & m));
                }
                if ((i & m)) numSet++;
            }
            numSets.push_back(numSet);
        }
        //std::cout << opCount << " A " << costReverse << " " << costNormal << std::endl;

        std::vector<double> probTrue;
        double shift = 0.0;
        for (int i = 0; i < N; i++) {
          double prob = (numSets[maxAns[i]] - shift) / (double) (maxAns[i] + 1);
          probTrue.push_back(prob);
          shift += prob;
        }

        std::sort(order.begin(), order.end(), [&](int i, int j) {
          return probTrue[i] > probTrue[j];
        });

        //std::cout << probTrue[order[0]] << std::endl;

        for (int i: order) {
            if (fixedB.find(i) != fixedB.end()) continue;

            int totalStart = ansCounts[ans[i]];
            int numChanged = numIncr[ans[i]];
            int numStay = numSame[ans[i]];

            int maxIncr = totalStart / 2;
            int maxStay = totalStart - maxIncr;

            bool incr;
            if (numChanged == maxIncr) {
                incr = false;
            } else if (numStay == maxStay) {
                incr = true;
            } else if (ans[i] + m > maxAns[i]) {
                incr = false;
            } else {
                int tmp = query();
                setInMachine(b[i], !inMachine[b[i]]);
                incr = query() == tmp;
                if (invert) incr = !incr;
            }
            
            if (incr) {
                numIncr[ans[i]]++;
                ans[i] += m;
            } else {
                numSame[ans[i]]++;
            }
        }

        m <<= 1;
    }

    for (int i = 0; i < N; i++) {
        Answer(b[i], a[ans[i]]);
    }

    std::cout << numSaved << std::endl;
}

#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::mt19937 rng(0);
  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);
  return 0;
}
#endif

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