oj.uz

Submission #398488

# Submission time Handle Problem Language Result Execution time Memory
398488 2021-05-04T11:40:39 Z model_code The Collection Game (BOI21_swaps) C++17
100 / 100
 8 ms 388 KB 
#include "swaps.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> r;
vector<pair<int, int>> queries;

void scheduleSortingNetwork(int i, int j) {
  schedule(r[i], r[j]);
  queries.emplace_back(i, j);
}

void visitSortingNetwork() {
  if (queries.size() == 0)
    return;
  vector<int> res = visit();
  for (int i = 0; i < (int) res.size(); i++)
    if (!res[i])
      swap(r[queries[i].first], r[queries[i].second]);
  queries.clear();
}

void answerSortingNetwork() {
  answer(r);
}

void solve(int N, int Q) {
  for (int i = 1; i <= N; i++)
    r.push_back(i);
  for (int k = 2; k <= 2 * N; k <<= 1) {
    for (int i = 0; i < N; i++) {
      int l = i ^ (k - 1);
      if (i < l && l < N)
        scheduleSortingNetwork(i, l);
    }
    visitSortingNetwork();
    for (int j = k >> 2; j > 0; j >>= 1) {
      for (int i = 0; i < N; i++) {
        int l = i ^ j;
        if (i < l && l < N)
          scheduleSortingNetwork(i, l);
      }
      visitSortingNetwork();
    }
  }
  answerSortingNetwork();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 7 ms 300 KB Correct
5 Correct 6 ms 304 KB Correct
6 Correct 5 ms 300 KB Correct
7 Correct 6 ms 304 KB Correct
8 Correct 6 ms 300 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 292 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 304 KB Correct
5 Correct 5 ms 300 KB Correct
6 Correct 7 ms 300 KB Correct
7 Correct 7 ms 296 KB Correct
8 Correct 6 ms 296 KB Correct
9 Correct 7 ms 296 KB Correct
10 Correct 5 ms 296 KB Correct
11 Correct 7 ms 304 KB Correct
12 Correct 6 ms 388 KB Correct
13 Correct 7 ms 296 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 200 KB Correct
3 Correct 1 ms 200 KB Correct
4 Correct 2 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 7 ms 296 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 7 ms 296 KB Correct
5 Correct 1 ms 200 KB Correct
6 Correct 2 ms 200 KB Correct
7 Correct 3 ms 200 KB Correct
8 Correct 5 ms 292 KB Correct
9 Correct 6 ms 300 KB Correct
10 Correct 6 ms 304 KB Correct
11 Correct 5 ms 300 KB Correct
12 Correct 7 ms 296 KB Correct
13 Correct 1 ms 200 KB Correct
14 Correct 2 ms 200 KB Correct
15 Correct 3 ms 200 KB Correct
16 Correct 6 ms 300 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 300 KB Correct
5 Correct 7 ms 296 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 300 KB Correct
5 Correct 7 ms 296 KB Correct
6 Correct 1 ms 200 KB Correct
7 Correct 2 ms 200 KB Correct
8 Correct 4 ms 200 KB Correct
9 Correct 6 ms 300 KB Correct
10 Correct 6 ms 296 KB Correct
11 Correct 5 ms 296 KB Correct
12 Correct 6 ms 384 KB Correct
13 Correct 7 ms 304 KB Correct
14 Correct 6 ms 296 KB Correct
15 Correct 6 ms 296 KB Correct
16 Correct 8 ms 296 KB Correct
17 Correct 5 ms 300 KB Correct
18 Correct 5 ms 300 KB Correct
19 Correct 1 ms 200 KB Correct
20 Correct 2 ms 200 KB Correct
21 Correct 3 ms 200 KB Correct
22 Correct 6 ms 300 KB Correct
23 Correct 6 ms 304 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 288 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 300 KB Correct
5 Correct 6 ms 296 KB Correct
6 Correct 6 ms 276 KB Correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 288 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 300 KB Correct
5 Correct 6 ms 296 KB Correct
6 Correct 6 ms 276 KB Correct
7 Correct 1 ms 200 KB Correct
8 Correct 2 ms 200 KB Correct
9 Correct 3 ms 200 KB Correct
10 Correct 6 ms 296 KB Correct
11 Correct 5 ms 300 KB Correct
12 Correct 6 ms 296 KB Correct
13 Correct 5 ms 300 KB Correct
14 Correct 6 ms 300 KB Correct
15 Correct 5 ms 304 KB Correct
16 Correct 7 ms 296 KB Correct
17 Correct 6 ms 300 KB Correct
18 Correct 6 ms 300 KB Correct
19 Correct 7 ms 296 KB Correct
20 Correct 1 ms 200 KB Correct
21 Correct 1 ms 288 KB Correct
22 Correct 3 ms 200 KB Correct
23 Correct 6 ms 296 KB Correct
24 Correct 6 ms 280 KB Correct
25 Correct 6 ms 280 KB Correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 300 KB Correct
5 Correct 6 ms 284 KB Correct
6 Correct 6 ms 280 KB Correct
7 Correct 6 ms 280 KB Correct

Subtask #12
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 6 ms 300 KB Correct
5 Correct 6 ms 284 KB Correct
6 Correct 6 ms 280 KB Correct
7 Correct 6 ms 280 KB Correct
8 Correct 1 ms 200 KB Correct
9 Correct 1 ms 200 KB Correct
10 Correct 2 ms 200 KB Correct
11 Correct 3 ms 200 KB Correct
12 Correct 5 ms 304 KB Correct
13 Correct 6 ms 296 KB Correct
14 Correct 7 ms 304 KB Correct
15 Correct 6 ms 296 KB Correct
16 Correct 6 ms 300 KB Correct
17 Correct 6 ms 296 KB Correct
18 Correct 7 ms 300 KB Correct
19 Correct 6 ms 300 KB Correct
20 Correct 5 ms 296 KB Correct
21 Correct 6 ms 300 KB Correct
22 Correct 1 ms 200 KB Correct
23 Correct 2 ms 200 KB Correct
24 Correct 3 ms 200 KB Correct
25 Correct 6 ms 300 KB Correct
26 Correct 6 ms 276 KB Correct
27 Correct 6 ms 276 KB Correct
28 Correct 6 ms 280 KB Correct