oj.uz

Submission #705337

# Submission time Handle Problem Language Result Execution time Memory
705337 2023-03-04T03:54:22 Z cig32 The Collection Game (BOI21_swaps) C++17
100 / 100
 20 ms 492 KB 
#include "swaps.h"
#include "bits/stdc++.h"
using namespace std;


mt19937_64 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}
int p[501], pos[501];
void solve(int N, int V) {
  // TODO implement this function
  for(int i=1; i<=N; i++) p[i] = pos[i] = i;
  for(int k=2; k<=(N<<1); k<<=1) {
    vector<pair<int,int> > queries;
    for(int i=0; i<N; i++) {
      int l = i ^ (k-1);
      if(i<l && l<N) {
        queries.push_back({p[i+1], p[l+1]});
      }
    }
    for(pair<int,int> x: queries) schedule(x.first,x.second);
    vector<int> res = visit();
    for(int i=0; i<res.size(); i++) {
      if(res[i] == 0) {
        // Then A[i] > A[j]
        swap(p[pos[queries[i].first]], p[pos[queries[i].second]]);
        for(int j=1; j<=N; j++) pos[p[j]] = j;
      }
    }
    for(int j=k>>2; j>=1; j>>=1) {
      queries.clear();
      for(int i=0; i<N; i++) {
        int l = i^j;
        if(i<l && l<N) {
          queries.push_back({p[i+1], p[l+1]});
        }
      }
      for(pair<int,int> x: queries) schedule(x.first,x.second);
      vector<int> res = visit();
      for(int i=0; i<res.size(); i++) {
        if(res[i] == 0) {
          // Then A[i] > A[j]
          swap(p[pos[queries[i].first]], p[pos[queries[i].second]]);
          for(int j=1; j<=N; j++) pos[p[j]] = j;
        }
      }
    }
  }
  
  vector<int> identity;
  for(int i=1; i<=N; i++) identity.push_back(p[i]);
  answer(identity);
}

Compilation message

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0; i<res.size(); i++) {
      |                  ~^~~~~~~~~~~
swaps.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |       for(int i=0; i<res.size(); i++) {
      |                    ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 4 ms 208 KB Correct
4 Correct 13 ms 316 KB Correct
5 Correct 4 ms 312 KB Correct
6 Correct 19 ms 316 KB Correct
7 Correct 13 ms 308 KB Correct
8 Correct 12 ms 312 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 4 ms 208 KB Correct
4 Correct 12 ms 424 KB Correct
5 Correct 4 ms 316 KB Correct
6 Correct 19 ms 320 KB Correct
7 Correct 14 ms 312 KB Correct
8 Correct 11 ms 312 KB Correct
9 Correct 12 ms 316 KB Correct
10 Correct 4 ms 312 KB Correct
11 Correct 18 ms 320 KB Correct
12 Correct 12 ms 316 KB Correct
13 Correct 12 ms 316 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 304 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 304 KB Correct
3 Correct 1 ms 208 KB Correct
4 Correct 1 ms 208 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 6 ms 316 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 6 ms 316 KB Correct
5 Correct 1 ms 208 KB Correct
6 Correct 1 ms 208 KB Correct
7 Correct 4 ms 208 KB Correct
8 Correct 12 ms 312 KB Correct
9 Correct 5 ms 420 KB Correct
10 Correct 17 ms 492 KB Correct
11 Correct 12 ms 316 KB Correct
12 Correct 12 ms 316 KB Correct
13 Correct 0 ms 208 KB Correct
14 Correct 1 ms 208 KB Correct
15 Correct 4 ms 208 KB Correct
16 Correct 12 ms 316 KB Correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 2 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 316 KB Correct
5 Correct 6 ms 296 KB Correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 2 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 316 KB Correct
5 Correct 6 ms 296 KB Correct
6 Correct 1 ms 208 KB Correct
7 Correct 6 ms 308 KB Correct
8 Correct 6 ms 324 KB Correct
9 Correct 12 ms 320 KB Correct
10 Correct 6 ms 316 KB Correct
11 Correct 20 ms 312 KB Correct
12 Correct 14 ms 316 KB Correct
13 Correct 12 ms 316 KB Correct
14 Correct 12 ms 316 KB Correct
15 Correct 4 ms 316 KB Correct
16 Correct 20 ms 312 KB Correct
17 Correct 12 ms 432 KB Correct
18 Correct 12 ms 316 KB Correct
19 Correct 1 ms 208 KB Correct
20 Correct 1 ms 304 KB Correct
21 Correct 4 ms 208 KB Correct
22 Correct 12 ms 316 KB Correct
23 Correct 13 ms 316 KB Correct

Subtask #9
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 308 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 320 KB Correct
5 Correct 4 ms 304 KB Correct
6 Correct 5 ms 296 KB Correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 1 ms 308 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 4 ms 320 KB Correct
5 Correct 4 ms 304 KB Correct
6 Correct 5 ms 296 KB Correct
7 Correct 0 ms 208 KB Correct
8 Correct 1 ms 208 KB Correct
9 Correct 3 ms 208 KB Correct
10 Correct 12 ms 308 KB Correct
11 Correct 4 ms 412 KB Correct
12 Correct 20 ms 436 KB Correct
13 Correct 12 ms 316 KB Correct
14 Correct 10 ms 316 KB Correct
15 Correct 12 ms 316 KB Correct
16 Correct 4 ms 316 KB Correct
17 Correct 20 ms 316 KB Correct
18 Correct 12 ms 316 KB Correct
19 Correct 11 ms 316 KB Correct
20 Correct 1 ms 208 KB Correct
21 Correct 2 ms 208 KB Correct
22 Correct 4 ms 208 KB Correct
23 Correct 12 ms 316 KB Correct
24 Correct 13 ms 300 KB Correct
25 Correct 12 ms 300 KB Correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 6 ms 316 KB Correct
5 Correct 4 ms 296 KB Correct
6 Correct 4 ms 292 KB Correct
7 Correct 4 ms 296 KB Correct

Subtask #12
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 1 ms 208 KB Correct
3 Correct 2 ms 208 KB Correct
4 Correct 6 ms 316 KB Correct
5 Correct 4 ms 296 KB Correct
6 Correct 4 ms 292 KB Correct
7 Correct 4 ms 296 KB Correct
8 Correct 0 ms 208 KB Correct
9 Correct 1 ms 208 KB Correct
10 Correct 2 ms 208 KB Correct
11 Correct 4 ms 292 KB Correct
12 Correct 12 ms 384 KB Correct
13 Correct 4 ms 312 KB Correct
14 Correct 18 ms 312 KB Correct
15 Correct 12 ms 312 KB Correct
16 Correct 11 ms 316 KB Correct
17 Correct 12 ms 424 KB Correct
18 Correct 4 ms 316 KB Correct
19 Correct 19 ms 312 KB Correct
20 Correct 13 ms 316 KB Correct
21 Correct 14 ms 312 KB Correct
22 Correct 1 ms 224 KB Correct
23 Correct 1 ms 208 KB Correct
24 Correct 5 ms 208 KB Correct
25 Correct 12 ms 436 KB Correct
26 Correct 13 ms 292 KB Correct
27 Correct 13 ms 292 KB Correct
28 Correct 13 ms 292 KB Correct