Submission #923273

#	Time	Username	Problem	Language	Result	Execution time	Memory
923273		nguyentunglam	Shuffle (NOI19_shuffle)	C++17	19 / 100	1 ms	604 KiB

shuffle

#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;

const int NN = 1e3 + 10;

int n, b, k;

int g1[NN], g2[NN], match1[NN], match2[NN];

int lab[NN];

void reset (vector<vector<int> > &arr) {
  for(int i = 0; i < arr.size(); i++) arr[i].clear();
}

int id (int x) {
  return (x + k - 1) / k;
}

vector<int> solve_2 () {
  int cnt = 0;

  vector<vector<int> > ask(b);
  vector<int> ret, unique1, unique2;
  for(int i = 1; i <= n; i++) ask[id(i) - 1].push_back(i);
  vector<vector<int> > tmp1 = shuffle(ask);
  for(auto &arr: tmp1) {
    ++cnt;
    for(auto &j : arr) g1[j] = cnt;
    match1[arr[0]] = arr[1];
    match1[arr[1]] = arr[0];
  } cnt = 0;

  for(int i = 1; i + 1 < b; i++) swap(ask[i].back(), ask[i + 1].back());
  vector<vector<int> > tmp3 = shuffle(ask);for(auto &arr : tmp3) {
    bool ok = 1;
    int group = g1[arr[0]];
    for(auto &j : arr) ok &= g1[j] == group;
    if (ok) unique1 = arr;
  }
  reset(ask);

  for(int i = 2; i <= n; i++) ask[id(i - 1) - 1].push_back(i);
  ask[b - 1].push_back(1);
  vector<vector<int> > tmp2 = shuffle(ask);
  for(auto &arr : tmp2) {
    ++cnt;
    for(auto &j : arr) g2[j] = cnt;
    match2[arr[0]] = arr[1];
    match2[arr[1]] = arr[0];
  } cnt = 0;

  for(int i = 0; i + 2 < b; i++) swap(ask[i].back(), ask[i + 1].back());
  vector<vector<int> > tmp4 = shuffle(ask);
  for(auto &arr : tmp4) {
    bool ok = 1;
    int group = g2[arr[0]];
    for(auto &j : arr) ok &= g2[j] == group;
    if (ok) unique2 = arr;
  }
  reset(ask);

  assert(!unique1.empty());
  assert(!unique2.empty());

  for(int &j : unique1) for(int &k : unique2) if (j == k) lab[1] = j;
  assert(lab[1]);

  for(int i = 1; i < n; i++) {
    if (i % 2) lab[i + 1] = match1[lab[i]];
    else lab[i + 1] = match2[lab[i]];
  }

  #ifdef ngu
  for(int i = 1; i <= n; i++) cout << lab[i] << " "; cout << endl;
  #endif // ngu

  for(int i = 1; i <= n; i++) ret.push_back(lab[i]);
  return ret;
}

vector<int> solve_3 () {
  vector<int> ret;
  return ret;
}

vector<int> solve(int N, int B, int K, int Q, int ST) {
  n = N;
  b = B;
  k = K;
  if (k == 2) return solve_2();
  return solve_3();
}

Compilation message (stderr)

shuffle.cpp: In function 'void reset(std::vector<std::vector<int> >&)':
shuffle.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i = 0; i < arr.size(); i++) arr[i].clear();
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 3 / 3
• Subtask 3: 0 / 12
• Subtask 4: 16 / 16
• Subtask 5: 0 / 15
• Subtask 6: 0 / 52