oj.uz

Submission #1052808

# Submission time Handle Problem Language Result Execution time Memory
1052808 2024-08-11T00:43:29 Z That_Salamander Minerals (JOI19_minerals) C++17
90 / 100
 90 ms 7352 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];
int maxAns[50000];

std::vector<int> a, b;

void Solve(int N) {
    std::vector<int> order(2 * N);
    std::iota(order.begin(), order.end(), 1);
    std::mt19937 rng(time(NULL));
    std::shuffle(order.begin(), order.end(), rng);

    for (int i = 1; i <= 2 * N; i++) {
        int prev = query();
        setInMachine(i, true);
        if (prev != query()) {
            a.push_back(i);
        } else {
            maxAns[b.size()] = a.size() - 1;
            b.push_back(i);
        }
    }

    std::vector<bool> fixed(N);

    int m = 1;
    while (m < N) {
        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[i] != 1)
                setInMachine(a[i], (i & m));
        }

        std::unordered_map<int, int> numIncr, numSame;

        std::vector<int> order(N);
        std::iota(order.begin(), order.end(), 0);
        std::shuffle(order.begin(), order.end(), rng);

        for (int i: order) {
            int totalStart = ansCounts[ans[i]];
            int numChanged = numIncr[ans[i]];
            int numStay = numSame[ans[i]];

            int maxIncr = totalStart / 2;
            int maxStay = totalStart - maxIncr;

            bool incr;
            if (numChanged == maxIncr) {
                incr = false;
            } else if (numStay == maxStay) {
                incr = true;
            } else {
                int tmp = query();
                setInMachine(b[i], !inMachine[b[i]]);
                incr = query() == tmp;
            }

            
            if (incr) {
                numIncr[ans[i]]++;
                ans[i] += m;
            } else {
                numSame[ans[i]]++;
            }
        }

        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)) {
    printf("Query(%d)\n", x);
    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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 5 ms 856 KB Output is correct
4 Correct 11 ms 1368 KB Output is correct
5 Correct 21 ms 2484 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory 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 1 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 21 ms 2484 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 14 ms 1888 KB Output is correct
12 Correct 22 ms 2484 KB Output is correct
13 Correct 22 ms 2476 KB Output is correct
14 Correct 21 ms 2476 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory 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 1 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 21 ms 2484 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 14 ms 1888 KB Output is correct
12 Correct 22 ms 2484 KB Output is correct
13 Correct 22 ms 2476 KB Output is correct
14 Correct 21 ms 2476 KB Output is correct
15 Correct 70 ms 6752 KB Output is correct
16 Correct 69 ms 6740 KB Output is correct
17 Correct 69 ms 6876 KB Output is correct
18 Correct 77 ms 6752 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory 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 1 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 21 ms 2484 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 14 ms 1888 KB Output is correct
12 Correct 22 ms 2484 KB Output is correct
13 Correct 22 ms 2476 KB Output is correct
14 Correct 21 ms 2476 KB Output is correct
15 Correct 70 ms 6752 KB Output is correct
16 Correct 69 ms 6740 KB Output is correct
17 Correct 69 ms 6876 KB Output is correct
18 Correct 77 ms 6752 KB Output is correct
19 Correct 71 ms 6896 KB Output is correct
20 Correct 75 ms 7008 KB Output is correct
21 Correct 70 ms 6876 KB Output is correct
22 Correct 67 ms 6816 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory 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 1 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 21 ms 2484 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 14 ms 1888 KB Output is correct
12 Correct 22 ms 2484 KB Output is correct
13 Correct 22 ms 2476 KB Output is correct
14 Correct 21 ms 2476 KB Output is correct
15 Correct 70 ms 6752 KB Output is correct
16 Correct 69 ms 6740 KB Output is correct
17 Correct 69 ms 6876 KB Output is correct
18 Correct 77 ms 6752 KB Output is correct
19 Correct 71 ms 6896 KB Output is correct
20 Correct 75 ms 7008 KB Output is correct
21 Correct 70 ms 6876 KB Output is correct
22 Correct 67 ms 6816 KB Output is correct
23 Correct 76 ms 7008 KB Output is correct
24 Correct 74 ms 7008 KB Output is correct
25 Correct 71 ms 7140 KB Output is correct
26 Correct 73 ms 6844 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory 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 1 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 21 ms 2484 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 14 ms 1888 KB Output is correct
12 Correct 22 ms 2484 KB Output is correct
13 Correct 22 ms 2476 KB Output is correct
14 Correct 21 ms 2476 KB Output is correct
15 Correct 70 ms 6752 KB Output is correct
16 Correct 69 ms 6740 KB Output is correct
17 Correct 69 ms 6876 KB Output is correct
18 Correct 77 ms 6752 KB Output is correct
19 Correct 71 ms 6896 KB Output is correct
20 Correct 75 ms 7008 KB Output is correct
21 Correct 70 ms 6876 KB Output is correct
22 Correct 67 ms 6816 KB Output is correct
23 Correct 76 ms 7008 KB Output is correct
24 Correct 74 ms 7008 KB Output is correct
25 Correct 71 ms 7140 KB Output is correct
26 Correct 73 ms 6844 KB Output is correct
27 Correct 80 ms 7264 KB Output is correct
28 Correct 76 ms 7264 KB Output is correct
29 Correct 80 ms 7148 KB Output is correct
30 Correct 71 ms 7056 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory 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 1 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 21 ms 2484 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 14 ms 1888 KB Output is correct
12 Correct 22 ms 2484 KB Output is correct
13 Correct 22 ms 2476 KB Output is correct
14 Correct 21 ms 2476 KB Output is correct
15 Correct 70 ms 6752 KB Output is correct
16 Correct 69 ms 6740 KB Output is correct
17 Correct 69 ms 6876 KB Output is correct
18 Correct 77 ms 6752 KB Output is correct
19 Correct 71 ms 6896 KB Output is correct
20 Correct 75 ms 7008 KB Output is correct
21 Correct 70 ms 6876 KB Output is correct
22 Correct 67 ms 6816 KB Output is correct
23 Correct 76 ms 7008 KB Output is correct
24 Correct 74 ms 7008 KB Output is correct
25 Correct 71 ms 7140 KB Output is correct
26 Correct 73 ms 6844 KB Output is correct
27 Correct 80 ms 7264 KB Output is correct
28 Correct 76 ms 7264 KB Output is correct
29 Correct 80 ms 7148 KB Output is correct
30 Correct 71 ms 7056 KB Output is correct
31 Correct 78 ms 7352 KB Output is correct
32 Correct 90 ms 7152 KB Output is correct
33 Correct 74 ms 7220 KB Output is correct
34 Correct 74 ms 7096 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory 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 1 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 21 ms 2484 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 14 ms 1888 KB Output is correct
12 Correct 22 ms 2484 KB Output is correct
13 Correct 22 ms 2476 KB Output is correct
14 Correct 21 ms 2476 KB Output is correct
15 Correct 70 ms 6752 KB Output is correct
16 Correct 69 ms 6740 KB Output is correct
17 Correct 69 ms 6876 KB Output is correct
18 Correct 77 ms 6752 KB Output is correct
19 Correct 71 ms 6896 KB Output is correct
20 Correct 75 ms 7008 KB Output is correct
21 Correct 70 ms 6876 KB Output is correct
22 Correct 67 ms 6816 KB Output is correct
23 Correct 76 ms 7008 KB Output is correct
24 Correct 74 ms 7008 KB Output is correct
25 Correct 71 ms 7140 KB Output is correct
26 Correct 73 ms 6844 KB Output is correct
27 Correct 80 ms 7264 KB Output is correct
28 Correct 76 ms 7264 KB Output is correct
29 Correct 80 ms 7148 KB Output is correct
30 Correct 71 ms 7056 KB Output is correct
31 Correct 78 ms 7352 KB Output is correct
32 Correct 90 ms 7152 KB Output is correct
33 Correct 74 ms 7220 KB Output is correct
34 Correct 74 ms 7096 KB Output is correct
35 Incorrect 69 ms 5824 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -