oj.uz

Submission #500188

# Submission time Handle Problem Language Result Execution time Memory
500188 2021-12-30T12:31:49 Z 600Mihnea JOIRIS (JOI16_joiris) C++17
0 / 100
 1 ms 204 KB 
/**

Enjoy JOI is the new
Enjoy EJOI

**/

#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 7;
int n;
int k;
int a[N];
int s[N];
vector<pair<int, int>> sol;

void gravity() {
  int mn = a[0];
  for (int i = 1; i < n; i++) {
    mn = min(mn, a[i]);
  }
  for (int i = 0; i < n; i++) {
    a[i] -= mn;
  }
}

void op1(int i) {
  sol.push_back({1, i});
  a[i] += k;
  gravity();
}

void op2(int l, int r) {
  assert(r - l + 1 == k);
  sol.push_back({2, l});
  for (int i = l; i <= r; i++) {
    a[i]++;
  }
  gravity();
}

void print() {
  return;
  int hmax = 0;
  for (int i = 0; i < n; i++) {
    hmax = max(hmax, a[i]);
  }
  for (int h = hmax; h >= 1; h--) {
    for (int i = 0; i < n; i++) {
      if (a[i] >= h) {
        cout << "x";
      } else {
        cout << " ";
      }
    }
    cout << "\n";
  }
  cout << "---------------------------------\n";
}

bool isok() {
  for (int i = 0; i < k; i++) {
    s[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    s[i % k] += a[i];
  }
  for (int i = 0; i <= n % k - 1; i++) {
    if (s[i] % k != s[0] % k) {
      return 0;
    }
  }
  for (int i = n % k; i < k; i++) {
    if (s[i] % k != s[k - 1] % k) {
      return 0;
    }
  }
  return 1;
}

int main() {
//  freopen ("input", "r", stdin);

  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }


  /**
  N = 5 =>
  a b a b a


  s(j) = sum of a[i] for i mod K = j
  update 1 : s(j) stays constant
  update 2 : relative s(j) stays constant
  delete update :
      relative s(0), s(1)..., s(N mod K - 1) stays constant
      relative s(N mod K), s(N mod K + 1)..., s(K - 1) stays constant

  **/

  if (!isok()) {
    cout << "-1\n";
    exit(0);
  }
  gravity();
  print();

  for (int i = 1; i < n; i++) {
    /// make a[i - 1] <= a[i]
    while (a[i - 1] > a[i]) {
      op1(i);
    }

  }


  for (int i = k - 1; i + 1 < n; i++) {
    /// make a[i] = a[i + 1]

    int steps = a[i + 1] - a[i];
    for (int step = 1; step <= steps; step++) {
      for (int j = i; j - k + 1 >= 0; j -= k) {
        sol.push_back({2, j});
      }

      if (i % k != k - 1) {
        for (int j = 0; j <= i % k; j++) {
          while (a[j] <= a[i + 1]) {
            a[j] += k;
          }
        }
      }
    }
    if (i % k != k - 1) {
      for (int j = 0; j <= i % k; j++) {
        a[j] -= steps;
      }
    }
    for (int j = i + 1; j < n; j++) {
      a[j] -= steps;
    }

    gravity();
    print();
    assert(a[i] == a[i + 1]);
  }

  assert(isok());
  for (int i = k - 1; i < n; i++) {
    assert(a[i] == a[k - 1]);
  }

  while (a[k - 1] > 0) {
    for (int i = 0; i <= k - 2; i++) {
      op1(i);
    }
  }
  for (int i = k - 1; i < n; i++) {
    assert(a[i] == 0);
  }
  assert(isok());



  for (int i = n % k; i < k; i++) {
    while (a[i] > 0) {
      for (int j = 0; j < n; j++) {
        while (a[j] < a[i]) {
          op1(j);
        }
      }
    }
  }
  cout << (int) sol.size() << "\n";
  for (auto &it : sol) {
    cout << it.first << " " << it.second + 1 << "\n";
  }

  return 0;
}
/**

    x
   xx
zzzxx
  xxx
  xxx
 xxxx
xxxxx

**/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -