Submission #1140732

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

int H = 50, W = 50, K = 8;
int B[50][50], used[50][50];
const double TL = 9.7;

void dump() {
}

int evaluate() {
  return 0;
}

void solve() {
  chrono::system_clock::time_point start = chrono::system_clock::now();

  random_device rnd;
  mt19937 mt(rnd());

  vector<pair<int, int>> ans;
  vector<vector<pair<int, int>>> pos(10);
  REP(i, H) REP(j, W) pos[B[i][j]].emplace_back(i, j);
  memset(used, 0, sizeof(used));
  for (int i = 9; i > 0; i--) {
    REP(j, pos[i].size()) {
      int sr, sc; tie(sr, sc) = pos[i][j];
      if (used[sr][sc]) continue;

      priority_queue<tuple<int, int, int>> pque;
      pque.emplace(-i, sr, sc);
      vector<pair<int, int>> cand;
      auto tmp_used = used;

      while (not pque.empty() and cand.size() < K) {
        int p, r, c; tie(p, r, c) = pque.top(); pque.pop();
        if (tmp_used[r][c]) continue;
        tmp_used[r][c] = true;
        cand.emplace_back(r, c);
        REP(d, 4) {
          int nr = r + dr[d], nc = c + dc[d];
          if (0 <= nr and nr < H and 0 <= nc and nc < W and not tmp_used[nr][nc] and B[nr][nc] != 0) {
            pque.emplace(-B[nr][nc], nr, nc);
          }
        }
      }

      if (cand.size() == K) {
        for (auto p : cand) {
          int r, c; tie(r, c) = p;
          used[r][c] = true;
          ans.emplace_back(r, c);
        }
      }
    }
  }

  printf("%d\n", ans.size() / K);
  for (auto p : ans) {
    printf("%d %d\n", p.first + 1, p.second + 1);
  }


  /*
  uniform_int_distribution<> rand3(0, 2);
  int itr = 0;

  while (true) {
    double diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;
    if (diff > TL) break;
    //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000. << ' ' << itr << ' ' << best_scores[0] << endl;
    itr++;
  }
  //cerr << itr << ' ' << best_scores[0] << endl;
  dump();*/
}

int main() {
  scanf("%d %d %d", &H, &W, &K);
  REP(i, H) {
    string row; cin >> row;
    REP(j, W) B[i][j] = row[j] - '0';
  }

  solve();

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:71:32: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::pair<int, int> >::size_type {aka long unsigned int}’ [-Wformat=]
   printf("%d\n", ans.size() / K);
                                ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:92:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &H, &W, &K);
                                ^

Judge Result