Submission #1169938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169938		aentrenus	Minerals (JOI19_minerals)	C++20	40 / 100	11 ms	1612 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
// using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using vb = std::vector<bool>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using str = std::string;
#define all(a) a.begin(), a.end()
#define print(a) for (auto elem:a) cout<<elem<<' '; cout<<'\n'
#define segprep(b) resize(1<<((int)ceil(log2(b.size()))+1))
#define FOR(a) for (int _ = 0; _ < a; _++)

int N;
vi stones;

void sort_out(int l, int r){
    if (r-l == 1) return;

    int s_l = l+N;
    if (r-l == 2){
        assert(Query(stones.at(l)) == 1);
        bool done = Query(stones.at(s_l)) == 1;
        Query(stones.at(s_l));
        Query(stones.at(l));
        if (!done){
            std::swap(stones.at(s_l), stones.at(s_l+1));
        }
        return;
    }
    int range_size = r-l,
        half_size = range_size/2,
        mid = l+half_size, s_mid = s_l+half_size, test_uniq;
    for (int i = l; i < mid; i++){
        test_uniq = Query(stones.at(i));
    }
    int l_uniq = mid-l, // wszystkie z lewej są unique
        s_swapper = s_mid;
    assert(test_uniq == l_uniq);
    for (int i = s_l; i < s_mid; i++){
        while(Query(stones.at(i)) != l_uniq){
            Query(stones.at(i));
            std::swap(stones.at(i), stones.at(s_swapper));
            s_swapper++;
        }
    }
    // czyszczenie szuflady
    for (int i = 0; i < half_size; i++){
        Query(stones.at(l+i));
        Query(stones.at(s_l+i));
    }
    sort_out(l, mid);
    sort_out(mid, r);
}

void solve2(){
    int mid = N;
    int swapper = mid;
    for (int i = 0; i < mid; i++){
        while(Query(stones.at(i)) != i+1){
            Query(stones.at(i));
            std::swap(stones.at(i), stones.at(swapper));
            swapper++;
        }
    }
    int test;
    for (int i = 0; i < N; i++){
        test = Query(stones.at(i));
    }
    assert(test == 0);

    sort_out(0, N);
    for (int i = 0; i < N; i++){
        Answer(stones.at(i), stones.at(i+N));
    }
}

void Solve(int N_){
    N = N_;
    stones.resize(2*N);
    for (int i = 0; i < 2*N; i++){
        stones.at(i) = i+1;
    }

    solve2();
}
/*
constexpr int MAX_N = 43000;
constexpr int MAX_CALLS = 1000000;

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];


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;
}

*/

• 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