Submission #929950

#	Time	Username	Problem	Language	Result	Execution time	Memory
929950		nguyentunglam	Shuffle (NOI19_shuffle)	C++17	100 / 100	4 ms	680 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], g3[NN], match1[NN], match2[NN];

int lab[NN], group[NN], g_val[NN], g_pos[NN], cnt[NN];

vector<int> arr_pos[NN];
vector<int> arr_val[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<vector<int> > ask(b);
  for(int i = 1; i <= n; i++) ask[id(i) - 1].push_back(i);
  vector<vector<int> > get1 = shuffle(ask);
  for(int i = 0; i < b; i++) {
    for(auto &j : get1[i]) g1[j] = i;
  }
  ask.clear();

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

  ask.resize(b);
  for(int i = 1; i <= n; i++) ask[id(i) - 1].push_back(i);
  for(int j = 1; j < k; j++) swap(ask[0][j], ask[1][j - 1]);
  vector<vector<int> > get3 = shuffle(ask);
  for(int i = 0; i < b; i++) {
    for(auto &j : get3[i]) g3[j] = i;
  }
  ask.clear();

  for(int val = 1; val <= n; val++) {
    bool ok = 1;
    for(int _val = 1; _val <= n; _val++) if (val != _val) {
      if (g1[val] == g1[_val]) {
        ok &= g2[val] != g2[_val];
        ok &= g3[val] != g3[_val];
      }
    }
    if (ok) {
      assert(lab[1] == 0);
      lab[1] = val;
    }
  }

  for(int loop = 1, x = 1; loop < b; loop++) {
    int old = x;
    for(int i = 0; i < b; i++) {
      int diff = 0, val = 0;
      for(auto &j : get2[i]) if (g1[j] != g1[lab[x]]) {
        diff++;
        val = j;
      }
      if (diff == 1) {
        x += k;
        lab[x] = val;
        assert(lab[x]);
        break;
      }
    }
    assert(x > old);
  }

  vector<vector<int> > pos, val;

  for(int x = 1; x <= n; x += k) {
    vector<int> tmp_pos, tmp_val;
    for(int i = x + 1; i <= x + k - 1; i++) {
      tmp_pos.push_back(i);
    }
    for(int i = 1; i <= n; i++) if (g1[lab[x]] == g1[i] && i != lab[x]) {
      tmp_val.push_back(i);
    }
    pos.push_back(tmp_pos);
    val.push_back(tmp_val);
  }

  for(int x = 1; x <= n; x += k) {
    group[lab[x]] = id(x);
  }

  for(int loop = 1; loop <= 12; loop++) {
    ask.clear();
    ask.resize(b);
    bool stop = 1;
    for(int i = 0; i < pos.size(); i++) stop &= pos[i].size() == 1;
    if (stop) break;
    vector<vector<int> > _pos, _val;
    for(int x = 1; x <= n; x += k) ask[id(x) - 1].push_back(x);
    assert(pos.size() == val.size());
    for(int i = 0; i < pos.size(); i++) {
      assert(pos[i].size() == val[i].size());
      int max_cnt = (pos[i].size() + b - 1) / b;
      for(auto &j : pos[i]) {
        int nxt = -1;
        for(int y = 0; y < b; y++) if (cnt[y] < max_cnt) {
          if (nxt == -1 || ask[nxt].size() > ask[y].size()) nxt = y;
        }
        assert(nxt >= 0);
        assert(ask[nxt].size() < k);
        ask[nxt].push_back(j);
        cnt[nxt]++;
        g_pos[j] = nxt;
      }
      for(int j = 0; j < b; j++) cnt[j] = 0;
    }

    for(int i = 0; i < b; i++) assert(ask[i].size() == k);
    vector<vector<int> > get = shuffle(ask);
    for(auto &arr : get) {
      int root = -1;
      for(auto &j : arr) {
        if (group[j]) {
          assert(root == -1);
          root = group[j] - 1;
        }
      }
      for(auto &j : arr) if (!group[j]) {
        g_val[j] = root;
      }
    }


    for(int i = 0; i < pos.size(); i++) {
      for(auto &j : pos[i]) arr_pos[g_pos[j]].push_back(j);
      for(auto &j : val[i]) arr_val[g_val[j]].push_back(j);
      for(int j = 0; j < b; j++) if (!arr_pos[j].empty()) {
        _pos.push_back(arr_pos[j]);
        _val.push_back(arr_val[j]);
        arr_pos[j].clear();
        arr_val[j].clear();
      }
    }

    pos = move(_pos);
    val = move(_val);
  }

  for(int i = 0; i < pos.size(); i++) {
    assert(pos[i].size() == 1);
    lab[pos[i][0]] = val[i][0];
  }

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

  vector<int> ret;
  for(int i = 1; i <= n; i++) ret.push_back(lab[i]);
  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:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int i = 0; i < arr.size(); i++) arr[i].clear();
      |                  ~~^~~~~~~~~~~~
shuffle.cpp: In function 'std::vector<int> solve_3()':
shuffle.cpp:167:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int i = 0; i < pos.size(); i++) stop &= pos[i].size() == 1;
      |                    ~~^~~~~~~~~~~~
shuffle.cpp:172:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for(int i = 0; i < pos.size(); i++) {
      |                    ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from shuffle.cpp:2:
shuffle.cpp:181:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  181 |         assert(ask[nxt].size() < k);
      |                ~~~~~~~~~~~~~~~~^~~
shuffle.cpp:189:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  189 |     for(int i = 0; i < b; i++) assert(ask[i].size() == k);
      |                                       ~~~~~~~~~~~~~~^~~~
shuffle.cpp:205:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |     for(int i = 0; i < pos.size(); i++) {
      |                    ~~^~~~~~~~~~~~
shuffle.cpp:220:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |   for(int i = 0; i < pos.size(); i++) {
      |                  ~~^~~~~~~~~~~~

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