Submission #5539580


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)

int H, W, K;
vector<vector<int>> cpt;
map<int, int> piece_size;
int current_piece_no = 10;

int dx[] = {0, 1};
int dy[] = {1, 0};

void make_piece(int y, int x, int selected_cpt) {
  if (selected_cpt >= K)
    return;

  cpt[y][x] = current_piece_no;
  piece_size[current_piece_no]++;

  int nx, ny;
  int mx, my, maxi = -1;
  rep(i, 2) {
    nx = x + dx[i];
    ny = y + dy[i];
    if (nx < 0 || nx >= W || ny < 0 || ny >= H)
      continue;
    if (cpt[ny][nx] >= 10)
      continue;
    if (cpt[ny][nx] > maxi) {
      mx = nx;
      my = ny;
      maxi = cpt[ny][nx];
    }
  }

  if (maxi != -1)
    make_piece(my, mx, selected_cpt + 1);
}

void dump_piece(int y, int x, int piece_no) {
  cout << y + 1 << " " << x + 1 << endl;

  cpt[y][x] = -1;

  int nx, ny;
  rep(i, 4) {
    nx = x + dx[i];
    ny = y + dy[i];
    if (nx < 0 || nx >= W || ny < 0 || ny >= H)
      continue;
    if (cpt[ny][nx] != piece_no)
      continue;
    dump_piece(ny, nx, piece_no);
  }
}

int main(void) {
  cin >> H >> W >> K;
  cpt.resize(H);

  string s;
  rep(i, H) {
    cpt[i].resize(W);
    cin >> s;
    rep(j, W) cpt[i][j] = s[j] - '0';
  }
  rep(i, H) rep(j, W) {
    if (cpt[i][j] >= 10) continue;
    make_piece(i, j, 0);
    current_piece_no++;
  }

  int C = 0;
  for (int i = 10; i <= current_piece_no; i++) {
    if (piece_size[i] != K) continue;
    C++;
  }
  cout << C << endl;

  rep(i, H) rep(j, W) {
    if (cpt[i][j] < 10) continue;
    if (piece_size[cpt[i][j]] != K) continue;
    dump_piece(i, j, cpt[i][j]);
  }
}

Submission Info

Submission Time
Task A - Multiple Pieces
User d2verb
Language C++14 (GCC 5.4.1)
Score 74257
Code Size 1750 Byte
Status AC
Exec Time 5 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘void dump_piece(int, int, int)’:
./Main.cpp:51:18: warning: iteration 2u invokes undefined behavior [-Waggressive-loop-optimizations]
     nx = x + dx[i];
                  ^
./Main.cpp:7:31: note: containing loop
 #define rep(i,n) for(int i=0;i<(n);i++)
                               ^
./Main.cpp:50:3: note: in expansion of macro ‘rep’
   rep(i, 4) {
   ^

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 7721 / 1343058 7000 / 1343058 8528 / 1343058 8511 / 1343058 8659 / 1343058 6349 / 1343058 6298 / 1343058 6643 / 1343058 7861 / 1343058 6687 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 5 ms 256 KB
subtask_01_02.txt AC 5 ms 256 KB
subtask_01_03.txt AC 5 ms 256 KB
subtask_01_04.txt AC 5 ms 256 KB
subtask_01_05.txt AC 5 ms 256 KB
subtask_01_06.txt AC 5 ms 256 KB
subtask_01_07.txt AC 5 ms 256 KB
subtask_01_08.txt AC 5 ms 256 KB
subtask_01_09.txt AC 5 ms 256 KB
subtask_01_10.txt AC 5 ms 256 KB