oj.uz

답안 #1052162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052162 2024-08-10T12:11:54 Z That_Salamander Minerals (JOI19_minerals) C++14
75 / 100
 25 ms 3252 KB 
#include <bits/stdc++.h>

void Solve(int N);
int Query(int x);

void Answer(int x, int y);

bool inMachine[100005];
int lastRes = 0;

void setInMachine(int i, bool val) {
    if (inMachine[i] != val) {
        lastRes = Query(i);
        inMachine[i] = val;
    }
}

int query() {
    return lastRes;
}

int ans[50000];

std::vector<int> a, b;

void Solve(int N) {
    for (int i = 1; i <= 2 * N; i++) {
        int prev = query();
        setInMachine(i, true);
        if (prev != query()) {
            a.push_back(i);
        } else {
            b.push_back(i);
        }
    }

    /*std::cout << "Sets: " << std::endl;

    std::cout << " ";
    for (int x: a) std::cout << " " << x;
    std::cout << std::endl;

    std::cout << " ";
    for (int x: b) std::cout << " " << x;
    std::cout << std::endl;*/

    int m = 1;
    while (m < N) {
        for (int i = 0; i < N; i++) {
            setInMachine(a[i], (i & m));
        }

        std::unordered_map<int, int> ansCounts;
        for (int i = 0; i < N; i++) ansCounts[ans[i]]++;

        for (int i = 0; i < N; i++) {
            if (ansCounts[ans[i]] == 1) continue;
            int tmp = query();
            setInMachine(b[i], !inMachine[b[i]]);
            if (query() == tmp) {
                ans[i] += m;
            }
        }

        m <<= 1;
    }

    for (int i = 0; i < N; i++) {
        Answer(b[i], a[ans[i]]);
    }
}

#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
#include <algorithm>

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 (N < 100)
    std::cout << "Answer(" << a << ", " << b << ")" << std::endl;
  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 secret_order[100000];

int main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }

  for (int i = 0; i < 2 * N; ++i) {
    secret_order[i] = i + 1;
  }

  std::mt19937 rng(0);
  std::shuffle(secret_order, secret_order + 2 * N, rng);

  for (int i = 1; i <= N; ++i) {
    int x, y;
    x = secret_order[2 * i - 2];
    y = secret_order[2 * i - 1];
    /*if (scanf("%d%d", &x, &y) != 2) {
      fprintf(stderr, "Error while reading input\n");
      exit(1);
    }*/
   if (N < 100)
   printf("%d %d\n", 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.0 / 6.0

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

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1440 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1368 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1440 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1368 KB Output is correct
15 Correct 21 ms 3068 KB Output is correct
16 Correct 24 ms 3132 KB Output is correct
17 Correct 14 ms 3208 KB Output is correct
18 Correct 14 ms 2912 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1440 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1368 KB Output is correct
15 Correct 21 ms 3068 KB Output is correct
16 Correct 24 ms 3132 KB Output is correct
17 Correct 14 ms 3208 KB Output is correct
18 Correct 14 ms 2912 KB Output is correct
19 Correct 21 ms 3252 KB Output is correct
20 Correct 25 ms 3152 KB Output is correct
21 Correct 14 ms 3120 KB Output is correct
22 Correct 14 ms 3016 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1440 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1368 KB Output is correct
15 Correct 21 ms 3068 KB Output is correct
16 Correct 24 ms 3132 KB Output is correct
17 Correct 14 ms 3208 KB Output is correct
18 Correct 14 ms 2912 KB Output is correct
19 Correct 21 ms 3252 KB Output is correct
20 Correct 25 ms 3152 KB Output is correct
21 Correct 14 ms 3120 KB Output is correct
22 Correct 14 ms 3016 KB Output is correct
23 Incorrect 18 ms 2384 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1440 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1368 KB Output is correct
15 Correct 21 ms 3068 KB Output is correct
16 Correct 24 ms 3132 KB Output is correct
17 Correct 14 ms 3208 KB Output is correct
18 Correct 14 ms 2912 KB Output is correct
19 Correct 21 ms 3252 KB Output is correct
20 Correct 25 ms 3152 KB Output is correct
21 Correct 14 ms 3120 KB Output is correct
22 Correct 14 ms 3016 KB Output is correct
23 Incorrect 18 ms 2384 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1440 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1368 KB Output is correct
15 Correct 21 ms 3068 KB Output is correct
16 Correct 24 ms 3132 KB Output is correct
17 Correct 14 ms 3208 KB Output is correct
18 Correct 14 ms 2912 KB Output is correct
19 Correct 21 ms 3252 KB Output is correct
20 Correct 25 ms 3152 KB Output is correct
21 Correct 14 ms 3120 KB Output is correct
22 Correct 14 ms 3016 KB Output is correct
23 Incorrect 18 ms 2384 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 3 ms 856 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 5 ms 1112 KB Output is correct
12 Correct 7 ms 1440 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 5 ms 1368 KB Output is correct
15 Correct 21 ms 3068 KB Output is correct
16 Correct 24 ms 3132 KB Output is correct
17 Correct 14 ms 3208 KB Output is correct
18 Correct 14 ms 2912 KB Output is correct
19 Correct 21 ms 3252 KB Output is correct
20 Correct 25 ms 3152 KB Output is correct
21 Correct 14 ms 3120 KB Output is correct
22 Correct 14 ms 3016 KB Output is correct
23 Incorrect 18 ms 2384 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -