Submission

P---xxxPx-

Score: 20

User: mistertfy64

Problemset: G.Peach's Backpack

Language: cpp

Time: 0.376 second

Submitted On: 2024-10-14 13:17:41

#include <bits/stdc++.h>
using namespace std;
#define CY(y, h) h - y

char current = 'A';

void advance() {
  if (current == 'Z') {
    current = 'A';
    return;
  }
  current++;
}

vector<vector<char>> backpack;

int main() {
  int N, M, Q, cn = 0;
  cin >> N >> M;
  cin >> Q;
  for (int i = 0; i < M; i++) {
    vector<char> row(N, '.');
    backpack.push_back(row);
  }

  set<int> wasted;
  vector<int> tm(N, 0);

  while (Q--) {
    cn++;
    int xi, yi, ki;
    bool ok = true;
    cin >> xi >> yi >> ki;
    int bottommost = 1;
    for (int i = ki - 1; i < ki + xi - 1; i++) {
      bottommost = max(bottommost, tm[i] + 1);
    }

    // insert
    int xs = ki - 1;
    int ys = bottommost + yi - 1;
    int xe = ki + (xi - 1) - 1;
    int ye = bottommost;

    if (ys > M) {
      wasted.insert(cn);
      ok = false;
    }

    // cerr << "cn:" << cn << "\n";
    // cerr << "Placing:" << xs << " " << ys << " " << xe << " " << ye << " "
    //<< bottommost << "\n";

    for (int y = ys; y >= ye; y--) {
      for (int x = xs; x <= xe; x++) {
        if (ok) {
          // cerr << "Placing " << current << " at " << CY(y, M) << " " << x
          //  << "\n";
          backpack[CY(y, M)][x] = current;
          tm[x]++;
        }
        advance();
      }
    }
  }

  for (int w : wasted) {
    cout << w << " ";
  }
  cout << "\n";

  for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
      cout << backpack[i][j];
    }
    cout << "\n";
  }

  return 0;
}