제출 #256243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256243		fedoseevtimofey	Minerals (JOI19_minerals)	C++14	40 / 100	38 ms	3316 KiB

minerals

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

#include "minerals.h"

void Solve(int N) {
  vector <int> gs_l;
  vector <int> gs_r;
  int cnt = 0;
  for (int i = 1; i <= 2 * N; ++i) {
    int cur_cnt = Query(i);
    if (cur_cnt > cnt) {
      cnt = cur_cnt;
      gs_l.push_back(i);
    } else {
      gs_r.push_back(i);
      Query(i);
    }
  }
  vector <int> f, s;
  function <void(vector <int>, vector <int>, int)> rec = [&] (vector <int> l, vector <int> r, int em) {
    if (l.size() == 1) {
      assert(r.size() == 1);
      f.push_back(l[0]);
      s.push_back(r[0]);
    } else {
      int m = (int)l.size() / 2;
      vector <int> l_l, l_r, r_l, r_r;
      for (int i = 0; i < m; ++i) l_l.push_back(l[i]);
      for (int i = m; i < (int)l.size(); ++i) l_r.push_back(l[i]);
      int have = -1;
      for (auto x : l_l) {
        have = Query(x);
      }
      if (!em) {
        for (auto x : r) {
          int cur = Query(x);
          if (cur > have) {
            r_l.push_back(x);
          } else {
            r_r.push_back(x);
          }
          Query(x);
        }
        rec(l_l, r_l, 1);
        rec(l_r, r_r, 0);
      } else {
        for (auto x : r) {
          int cur = Query(x);
          if (cur > have) {
            r_r.push_back(x);
          } else {
            r_l.push_back(x);
          }
          Query(x);
        }
        rec(l_l, r_l, 0);
        rec(l_r, r_r, 1); 
      }
    }
  };
  rec(gs_l, gs_r, 0);
  for (int i = 0; i < N; ++i) {
    Answer(f[i], s[i]);
  }
}

#ifdef LOCAL
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() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  cin >> N;
  for (int i = 1; i <= N; ++i) {
    int x, y;
    cin >> 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: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 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