답안 #220099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220099	2020-04-07T01:16:05 Z	rama_pang	Minerals (JOI19_minerals)	C++14	100 / 100	77 ms	4260 KB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 43005;
const int TOTAL_QUERIES = 999976;

int optimal_pivot(int n) {
  static vector<pair<int, int>> optimal(MAXN, make_pair(1e8, 1e8));
  static bool computed = false;

  if (computed) return optimal[n].second;

  computed = true;
  optimal[0] = optimal[1] = {0, 0};
  for (int i = 2; i < MAXN; i++) {
    int lo = 1, hi = i / 2;
    while (lo < hi) {
      int m1 = (lo + hi) / 2;
      int m2 = m1 + 1;
      int c1 = optimal[m1].first + optimal[i - m1].first + i - 1 + m1;
      int c2 = optimal[m2].first + optimal[i - m2].first + i - 1 + m2;
      if (c1 < c2) {
        hi = m1;
      } else {
        lo = m2;
      }
    }
    optimal[i] = make_pair(optimal[lo].first + optimal[i - lo].first + lo + i - 1, lo);
  }

  return optimal_pivot(n);
}

bool query(int x) {
  static int query_cnt = 0;
  static int last = -1;
  query_cnt++;
  int cur = Query(x);
  bool res = (cur == last);
  last = cur;
  assert(query_cnt <= TOTAL_QUERIES);
  return res;
}

void Solve(vector<int> A, vector<int> B, bool isBInside) {
  int n = A.size();
  if (n == 0) return;
  if (n == 1) return Answer(A[0], B[0]);

  int piv = optimal_pivot(n);
  vector<int> Aleft, Aright;
  vector<int> Bleft, Bright;
  if (isBInside) { // All of B is in the box, so we remove the second half
    for (int i = 0; i < n - piv; i++) {
      Bleft.emplace_back(B[i]);
    }
    for (int i = n - piv; i < n; i++) {
      Bright.emplace_back(B[i]);
      query(B[i]); // 
    }
  } else { // None of B is in the box, so we add the first half
    for (int i = 0; i < piv; i++) {
      Bleft.emplace_back(B[i]);
      query(B[i]); // add elemens in B such that only the first half remains
    }
    for (int i = piv; i < n; i++) {
      Bright.emplace_back(B[i]);
    }
  }

  for (int i = 0; i < n; i++) {
    if (Aright.size() == Bright.size()) {  
      Aleft.emplace_back(A[i]);   // all A[i] in the right half is matched
    } else if (Aleft.size() == Bleft.size()) { 
      Aright.emplace_back(A[i]);  // all A[i] in the left half is matched
    } else if (query(A[i])) {
      Aleft.emplace_back(A[i]);   // A[i] has a match is in the first half of B
    } else {
      Aright.emplace_back(A[i]);  // A[i] has a match in the second half of B
    }
  }

  return Solve(Aleft, Bleft, true), Solve(Aright, Bright, false);
}

void Solve(int N) {
  vector<int> A, B;
  for (int i = 1; i <= 2 * N; i++) {
    if (query(i)) { // the current element is already in the box
      B.emplace_back(i);
    } else { // the current element is a new element
      A.emplace_back(i);
    }
  }

  return Solve(A, B, true);
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	768 KB	Output is correct
2	Correct	10 ms	896 KB	Output is correct
3	Correct	12 ms	1024 KB	Output is correct
4	Correct	20 ms	1364 KB	Output is correct
5	Correct	30 ms	2024 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	8 ms	768 KB	Output is correct
6	Correct	10 ms	896 KB	Output is correct
7	Correct	12 ms	1024 KB	Output is correct
8	Correct	20 ms	1364 KB	Output is correct
9	Correct	30 ms	2024 KB	Output is correct
10	Correct	9 ms	768 KB	Output is correct
11	Correct	22 ms	1576 KB	Output is correct
12	Correct	30 ms	2024 KB	Output is correct
13	Correct	29 ms	2092 KB	Output is correct
14	Correct	27 ms	1884 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	8 ms	768 KB	Output is correct
6	Correct	10 ms	896 KB	Output is correct
7	Correct	12 ms	1024 KB	Output is correct
8	Correct	20 ms	1364 KB	Output is correct
9	Correct	30 ms	2024 KB	Output is correct
10	Correct	9 ms	768 KB	Output is correct
11	Correct	22 ms	1576 KB	Output is correct
12	Correct	30 ms	2024 KB	Output is correct
13	Correct	29 ms	2092 KB	Output is correct
14	Correct	27 ms	1884 KB	Output is correct
15	Correct	69 ms	4160 KB	Output is correct
16	Correct	63 ms	3952 KB	Output is correct
17	Correct	53 ms	3948 KB	Output is correct
18	Correct	59 ms	3788 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	8 ms	768 KB	Output is correct
6	Correct	10 ms	896 KB	Output is correct
7	Correct	12 ms	1024 KB	Output is correct
8	Correct	20 ms	1364 KB	Output is correct
9	Correct	30 ms	2024 KB	Output is correct
10	Correct	9 ms	768 KB	Output is correct
11	Correct	22 ms	1576 KB	Output is correct
12	Correct	30 ms	2024 KB	Output is correct
13	Correct	29 ms	2092 KB	Output is correct
14	Correct	27 ms	1884 KB	Output is correct
15	Correct	69 ms	4160 KB	Output is correct
16	Correct	63 ms	3952 KB	Output is correct
17	Correct	53 ms	3948 KB	Output is correct
18	Correct	59 ms	3788 KB	Output is correct
19	Correct	76 ms	4204 KB	Output is correct
20	Correct	69 ms	4048 KB	Output is correct
21	Correct	59 ms	3912 KB	Output is correct
22	Correct	56 ms	3828 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	8 ms	768 KB	Output is correct
6	Correct	10 ms	896 KB	Output is correct
7	Correct	12 ms	1024 KB	Output is correct
8	Correct	20 ms	1364 KB	Output is correct
9	Correct	30 ms	2024 KB	Output is correct
10	Correct	9 ms	768 KB	Output is correct
11	Correct	22 ms	1576 KB	Output is correct
12	Correct	30 ms	2024 KB	Output is correct
13	Correct	29 ms	2092 KB	Output is correct
14	Correct	27 ms	1884 KB	Output is correct
15	Correct	69 ms	4160 KB	Output is correct
16	Correct	63 ms	3952 KB	Output is correct
17	Correct	53 ms	3948 KB	Output is correct
18	Correct	59 ms	3788 KB	Output is correct
19	Correct	76 ms	4204 KB	Output is correct
20	Correct	69 ms	4048 KB	Output is correct
21	Correct	59 ms	3912 KB	Output is correct
22	Correct	56 ms	3828 KB	Output is correct
23	Correct	73 ms	4028 KB	Output is correct
24	Correct	66 ms	4024 KB	Output is correct
25	Correct	56 ms	4004 KB	Output is correct
26	Correct	64 ms	3864 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	8 ms	768 KB	Output is correct
6	Correct	10 ms	896 KB	Output is correct
7	Correct	12 ms	1024 KB	Output is correct
8	Correct	20 ms	1364 KB	Output is correct
9	Correct	30 ms	2024 KB	Output is correct
10	Correct	9 ms	768 KB	Output is correct
11	Correct	22 ms	1576 KB	Output is correct
12	Correct	30 ms	2024 KB	Output is correct
13	Correct	29 ms	2092 KB	Output is correct
14	Correct	27 ms	1884 KB	Output is correct
15	Correct	69 ms	4160 KB	Output is correct
16	Correct	63 ms	3952 KB	Output is correct
17	Correct	53 ms	3948 KB	Output is correct
18	Correct	59 ms	3788 KB	Output is correct
19	Correct	76 ms	4204 KB	Output is correct
20	Correct	69 ms	4048 KB	Output is correct
21	Correct	59 ms	3912 KB	Output is correct
22	Correct	56 ms	3828 KB	Output is correct
23	Correct	73 ms	4028 KB	Output is correct
24	Correct	66 ms	4024 KB	Output is correct
25	Correct	56 ms	4004 KB	Output is correct
26	Correct	64 ms	3864 KB	Output is correct
27	Correct	73 ms	4088 KB	Output is correct
28	Correct	72 ms	4220 KB	Output is correct
29	Correct	63 ms	4084 KB	Output is correct
30	Correct	56 ms	3944 KB	Output is correct

Subtask #8
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	8 ms	768 KB	Output is correct
6	Correct	10 ms	896 KB	Output is correct
7	Correct	12 ms	1024 KB	Output is correct
8	Correct	20 ms	1364 KB	Output is correct
9	Correct	30 ms	2024 KB	Output is correct
10	Correct	9 ms	768 KB	Output is correct
11	Correct	22 ms	1576 KB	Output is correct
12	Correct	30 ms	2024 KB	Output is correct
13	Correct	29 ms	2092 KB	Output is correct
14	Correct	27 ms	1884 KB	Output is correct
15	Correct	69 ms	4160 KB	Output is correct
16	Correct	63 ms	3952 KB	Output is correct
17	Correct	53 ms	3948 KB	Output is correct
18	Correct	59 ms	3788 KB	Output is correct
19	Correct	76 ms	4204 KB	Output is correct
20	Correct	69 ms	4048 KB	Output is correct
21	Correct	59 ms	3912 KB	Output is correct
22	Correct	56 ms	3828 KB	Output is correct
23	Correct	73 ms	4028 KB	Output is correct
24	Correct	66 ms	4024 KB	Output is correct
25	Correct	56 ms	4004 KB	Output is correct
26	Correct	64 ms	3864 KB	Output is correct
27	Correct	73 ms	4088 KB	Output is correct
28	Correct	72 ms	4220 KB	Output is correct
29	Correct	63 ms	4084 KB	Output is correct
30	Correct	56 ms	3944 KB	Output is correct
31	Correct	73 ms	4260 KB	Output is correct
32	Correct	71 ms	4144 KB	Output is correct
33	Correct	58 ms	4112 KB	Output is correct
34	Correct	58 ms	4108 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	7 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	8 ms	768 KB	Output is correct
6	Correct	10 ms	896 KB	Output is correct
7	Correct	12 ms	1024 KB	Output is correct
8	Correct	20 ms	1364 KB	Output is correct
9	Correct	30 ms	2024 KB	Output is correct
10	Correct	9 ms	768 KB	Output is correct
11	Correct	22 ms	1576 KB	Output is correct
12	Correct	30 ms	2024 KB	Output is correct
13	Correct	29 ms	2092 KB	Output is correct
14	Correct	27 ms	1884 KB	Output is correct
15	Correct	69 ms	4160 KB	Output is correct
16	Correct	63 ms	3952 KB	Output is correct
17	Correct	53 ms	3948 KB	Output is correct
18	Correct	59 ms	3788 KB	Output is correct
19	Correct	76 ms	4204 KB	Output is correct
20	Correct	69 ms	4048 KB	Output is correct
21	Correct	59 ms	3912 KB	Output is correct
22	Correct	56 ms	3828 KB	Output is correct
23	Correct	73 ms	4028 KB	Output is correct
24	Correct	66 ms	4024 KB	Output is correct
25	Correct	56 ms	4004 KB	Output is correct
26	Correct	64 ms	3864 KB	Output is correct
27	Correct	73 ms	4088 KB	Output is correct
28	Correct	72 ms	4220 KB	Output is correct
29	Correct	63 ms	4084 KB	Output is correct
30	Correct	56 ms	3944 KB	Output is correct
31	Correct	73 ms	4260 KB	Output is correct
32	Correct	71 ms	4144 KB	Output is correct
33	Correct	58 ms	4112 KB	Output is correct
34	Correct	58 ms	4108 KB	Output is correct
35	Correct	77 ms	4260 KB	Output is correct
36	Correct	71 ms	4260 KB	Output is correct
37	Correct	60 ms	4148 KB	Output is correct
38	Correct	60 ms	4256 KB	Output is correct

답안 #220099

Compilation message