Submission #1414372


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;
     
#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = (1LL << 31) - 1;
const ll MOD = 1e9 + 7;
     
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3
     
int h = 50, w = 50, k = 8;
string s[51];
bool f[51][51];

vector<pair<int, int> > make_piece(int y, int x, int l) {
	int dy[4] = { 1, -1, 0, 0 };
	int dx[4] = { 0, 0, 1, -1 };
	vector<pair<int, int> > res;
	queue<pair<int, int> > q;
	q.push(pair<int, int>(y, x));
	res.push_back(pair<int, int>(y, x));
	f[y][x] = true;
	while (!q.empty()) {
		pair<int, int> p = q.front(); q.pop();
		//cout << p.first << " " << p.second << endl;
		if ((int)res.size() == k) break;
		for (int i = 0; i < 4; i++) {
			int ny = p.first + dy[i];
			int nx = p.second + dx[i];
			if (!(0 <= ny && ny < h && 0 <= nx && nx < w) || f[ny][nx]) continue;
			if ((s[ny][nx] - '0') < l) continue;
			res.push_back(pair<int, int>(ny, nx));
			q.push(pair<int, int>(ny, nx));
			f[ny][nx] = true;
			if ((int)res.size() == k) break;
		}
	}
	if ((int)res.size() == k) return res;
	for (int i = 0; i < (int)res.size(); i++) {
		f[res[i].first][res[i].second] = false;
	}
	res.clear();
	return res;
}

int main() {
	cin >> h >> w >> k;
	for (int i = 0; i < h; i++) cin >> s[i];
	vector<vector<pair<int, int> > > ans;
	vector<pair<int, int> > tmp;
	for (int k = 2; k >= 1; k--) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (!f[i][j]) {
					tmp = make_piece(i, j, k);
					if (!tmp.empty())ans.push_back(tmp);
				}
			}
		}
	}
	int c = ans.size();
	cout << c << endl;
	for (int i = 0; i < c; i++) {
		//cout << ans[i].size() << endl;
		for (int j = 0; j < 8; j++) {
			cout << ans[i][j].first + 1 << " " << ans[i][j].second + 1 << endl;
		}
	}
}

Submission Info

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

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 7145 / 1343058 11206 / 1343058 12977 / 1343058 7164 / 1343058 9441 / 1343058 9588 / 1343058 10232 / 1343058 7248 / 1343058 9119 / 1343058 7181 / 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