oj.uz

답안 #836215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836215 2023-08-24T08:53:40 Z HollaFoil Minerals (JOI19_minerals) C++14
0 / 100
 131 ms 262144 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> m;
unordered_map<int, int> unm;
map<pair<int,int>, queue<int>> candidates;

int Q(int i) {
  return Query(m[i]+1);
}

void InitRand(int N) {
  srand(7);
  vector<int> order(2*N);
  for (int i = 0; i < 2*N; i++) order[i]=i;
  random_shuffle(order.begin(), order.end());
  random_shuffle(order.begin(), order.end());
  for (int i = 0; i < 2*N; i++) {
    m[i]=order[i];
    unm[order[i]]=i;
    //m[i] = i;
  }
}

pair<int,int> inserted;
vector<int> lefts;
int q = -1;

void prepareInterval(pair<int,int> interval, pair<int, int> full) {
  //cout << "Preparing intervals: " << "in - (" << inserted.first << "; " << inserted.second << ")  target - (" << interval.first << "; " << interval.second << ")\n";
  for (int i = full.first; i <= full.second; i++) {
    bool a = false;
    bool b = false;
    bool c = false;
    if (i >= inserted.first && i <= inserted.second) a = true;
    if (i >= interval.first && i <= interval.second) b = true;
    if (i >= full.first && i <= full.second) c = true;
    if (a != b && c) q = Q(lefts[i]);
  }
}

void search(int i, int j) {
  //cout << "Searching i=" << i << " j=" << j << endl;
  if (i == j) return;
  int diff = j - i + 1;
  int a = i;

  int b = a + (diff)/2;
  i = b + 1;
  pair<int, int> full = make_pair(a, j);
  pair<int, int> l = make_pair(a, b);
  pair<int, int> r = make_pair(i, j);
  prepareInterval(l, full);
  inserted = l;
  int lcount = b - a + 1;
  int rcount = j - i + 1;
  //cout << "L = (" << a << "; " << b << ")        R = (" << i << "; " << j << ")\n";
  while (!candidates[full].empty()) {
    int c = candidates[full].front();
    candidates[full].pop();
    //cout << "  Candidate " << c << " - ";

    if (lcount == 0) {
      candidates[r].push(c);
      rcount--;
      continue;
    }
    else if (rcount == 0) {
      candidates[l].push(c);
      lcount--;
      continue;
    }
    //cout << " (passed sanity) ";
    int next = Q(c);
    if (q == next) {
      candidates[l].push(c);
      lcount--;
      //cout << " left" << endl;
    }
    else {
      candidates[r].push(c);
      rcount--;
      //cout << " right" << endl;
    }
    q = next;
  }

  search(a, b);
  search(i, j);
}

void Solve(int N) {
  InitRand(N);
  pair<int,int> interval = make_pair(0, 2*N-1);
  for (int i = 0; i < 2*N; i++) {
    candidates[interval].push(i);
  }
  interval = make_pair(0, N-1);
  q = Q(0);
  lefts.push_back(0);
  for (int i = 1; i < 2*N; i++) {
    int next = Q(i);
    if (q == next) {
      candidates[interval].push(i);
    }
    else {
      q = next;
      lefts.push_back(i);
    }
  }
  inserted = make_pair(0, N-1);
  //cout << "Left: ";
  for (auto i : lefts) {
    //cout << i << " ";
  }

  search(0, N-1);
  for (int i = 0; i < N; i++) {
    int a = m[lefts[i]];
    int b = m[candidates[make_pair(i, i)].front()];
    //cout << a << " = " << b << endl;
    Answer(a+1, b+1);
  }


}
/*

4
0 4
1 5
2 3
6 7

*/

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:114:13: warning: unused variable 'i' [-Wunused-variable]
  114 |   for (auto i : lefts) {
      |             ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 128 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -