Submission #705337

#	Time	Username	Problem	Language	Result	Execution time	Memory
705337		cig32	The Collection Game (BOI21_swaps)	C++17	100 / 100	20 ms	492 KiB

swaps

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 6
• Subtask 7: 9 / 9
• Subtask 8: 6 / 6
• Subtask 9: 21 / 21
• Subtask 10: 14 / 14
• Subtask 11: 9 / 9
• Subtask 12: 6 / 6