oj.uz

Submission #923273

# Submission time Handle Problem Language Result Execution time Memory
923273 2024-02-07T04:37:14 Z nguyentunglam Shuffle (NOI19_shuffle) C++17
19 / 100
 1 ms 604 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer. Returned result not of length 6.
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Wrong Answer. Returned result not of length 999.
2 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #5
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 560 KB Wrong Answer. Returned result not of length 1000.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Wrong Answer. Returned result not of length 99.
2 Halted 0 ms 0 KB -