Submission #1314164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314164		mikolaj00	Minerals (JOI19_minerals)	C++20	Compilation error	0 ms	0 KiB

minerals

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <unordered_set>
#include <random>
#include <chrono>
#include "minerals.h"
using namespace std;

#define DEBUG true

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

vector<bool> in;
int cnt = 0;
bool call_query(int k)
{
    in[k] = !in[k];
    int old_cnt = cnt;
    cnt = Query(k);
    if (old_cnt != cnt)
        return true;
    else
        return false;
}

vector<pair<int, int>> ans;
void rec(vector<int> a, vector<int> b)
{
    if (a.size() == 1)
    {
        ans.push_back({a[0], b[0]});
        return;
    }

    int mid = a.size()/2;        
    vector<int> a1, b1, a2, b2;
    unordered_set<int> s;
    unordered_set<int> res;
    for (int i = a.size()-1-mid+1; i < a.size(); i++)
    {
      int k = uniform_int_distribution<int>(0, i-1)(mt);
      if (!s.count(k))
        res.insert(k);
      else
        res.insert(i);
    }

    int a1_cnt = 0, a2_cnt = 0;
    for (int i = 0; i < a.size(); i++)
    {
      if (res.count(i))
      {
        a1.push_back(a[i]);
        if (in[a[i]])
          a1_cnt++;
      }
      else
      {
        a2.push_back(a[i]);
        if (in[a[i]])
          a2_cnt++;
      }
    }

    if (a1_cnt < a2_cnt)
      swap(a1, a2);

    for (int i = 0; i < a1.size(); i++)
      if (!in[a1[i]])
        call_query(a1[i]);
    for (int i = 0; i < a2.size(); i++)
      if (in[a2[i]])
        call_query(a2[i]);

    for (int i = 0; i < b.size(); i++)
    {
        if (!call_query(b[i]))
            b1.push_back(b[i]);
        else
            b2.push_back(b[i]);
    }

    rec(a2, b2);
    rec(a1, b1);
}

void Solve(int N)
{
    in = vector<bool>(2*N+1);

    vector<pair<vector<int>, vector<int>>> nodes(1);
    for (int i = 1; i <= 2*N; i++)
    {
        if (call_query(i))
            nodes[0].second.push_back(i);
        else
        {
            nodes[0].first.push_back(i);
        }
    }

    rec(nodes[0].second, nodes[0].first);
    for (auto[a, b] : ans)
        Answer(a, b);
}

#if DEBUG
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)) {
    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 (++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 main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  for (int i = 1; i <= N; ++i) {
    int x, y;
    if (scanf("%d%d", &x, &y) != 2) {
      fprintf(stderr, "Error while reading input\n");
      exit(1);
    }
    counterpart[x] = y;
    counterpart[y] = x;
  }
  Solve(N);
  if (num_answers != N) {
    WrongAnswer(6);
  }
  printf("Accepted: %d\n", num_queries);
  return 0;
}
#endif

Compilation message (stderr)

minerals.cpp: In function 'int Query(int)':
minerals.cpp:142:7: error: reference to 'count' is ambiguous
  142 |     --count[type];
      |       ^~~~~
minerals.cpp:125:5: note: candidates are: 'int {anonymous}::count [86001]'
  125 | int count[2 * MAX_N + 1];
      |     ^~~~~
In file included from /usr/include/c++/13/chrono:48,
                 from minerals.cpp:6:
/usr/include/c++/13/bits/stl_algo.h:4072:5: note:                 'template<class _IIter, class _Tp> constexpr typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4072 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
minerals.cpp:143:9: error: reference to 'count' is ambiguous
  143 |     if (count[type] == 0) {
      |         ^~~~~
minerals.cpp:125:5: note: candidates are: 'int {anonymous}::count [86001]'
  125 | int count[2 * MAX_N + 1];
      |     ^~~~~
/usr/include/c++/13/bits/stl_algo.h:4072:5: note:                 'template<class _IIter, class _Tp> constexpr typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4072 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
minerals.cpp:148:7: error: reference to 'count' is ambiguous
  148 |     ++count[type];
      |       ^~~~~
minerals.cpp:125:5: note: candidates are: 'int {anonymous}::count [86001]'
  125 | int count[2 * MAX_N + 1];
      |     ^~~~~
/usr/include/c++/13/bits/stl_algo.h:4072:5: note:                 'template<class _IIter, class _Tp> constexpr typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4072 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
minerals.cpp:149:9: error: reference to 'count' is ambiguous
  149 |     if (count[type] == 1) {
      |         ^~~~~
minerals.cpp:125:5: note: candidates are: 'int {anonymous}::count [86001]'
  125 | int count[2 * MAX_N + 1];
      |     ^~~~~
/usr/include/c++/13/bits/stl_algo.h:4072:5: note:                 'template<class _IIter, class _Tp> constexpr typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4072 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~