OC'17-18 Round 1

gravity.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <climits>
#include <set>
#include <bitset>
#include <math.h>
#include <queue>
#include <map>
#include <sstream>
#include <functional>
#include <assert.h>
#include <unordered_map>
#include <unordered_set>
#include <complex>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::pair<double, double> pdd;
template <typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <typename T> using max_heap = std::priority_queue<T, std::vector<T>, std::less<T>>;

#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define TESTS(t) int NUMBER_OF_TESTS; cin >> NUMBER_OF_TESTS; for(int t = 1; t <= NUMBER_OF_TESTS; t++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ROF(i, start, end) for(int i = (start); i >= (end); i--)
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define PI (asin(1)*2)
#define OO ((1LL<<31)-1)
#define eps 1e-12
#define in(a, b)   ((b).find(a) != (b).end())
#define mp(a, b)   make_pair((a), (b))
#define sgn(a)     ((a) > eps ? 1 : ((a) < -eps ? -1 : 0))
#define cl1(x)     ((x)&((x)-1)) // clear lowest 1 bit
#define cl0(x)     ((x)|((x)+1)) // clear lowest 0 bit
#define ct1(x)     ((x)&((x)+1)) // clear all trailing 1 bits
#define pb push_back
#define MOD 1000000007
#define MAX_N 2000
using namespace std;

pair<int, int> dir[] = { {-1, 0}, {1,0}, {0,-1}, {0,1} };
ll ids[MAX_N+100][MAX_N+100];
bool grid[MAX_N+100][MAX_N+100];
bool newGrid[MAX_N+100][MAX_N+100];
int groups = 1;
pair<ll, ll> highestGroup[MAX_N+100];

vector<ll> groupFall;

// JUSTAS region
vector<pii>pieces[4100000];
int inPiece[2100][2100];
vector<int>willStop[2100];
bool hasStopped[4100000];
bool vis[2100][2100];
pii cellUp[2100][2100];
int N, M;
int pieceCount;
bool answer[2100][2100];

void dfs(int x, int y, int num) {
	if (x < 1 || y < 1)return;
	if (x > N || y > M)return;
	if (!grid[x][y])return;
	if (vis[x][y])return;
	vis[x][y] = true;
	inPiece[x][y] = num;
	pieces[num].push_back(pii(x, y));
	dfs(x + 1, y, num);
	dfs(x - 1, y, num);
	dfs(x, y + 1, num);
	dfs(x, y - 1, num);
}

#define fori(N)          for(int i = 0; i<(N); i++)
#define fori1(N)          for(int i = 1; i<=(N); i++)
#define forj(N)         for(int j = 0; j<(N); j++)
#define forj1(N)         for(int j = 1; j<=(N); j++)
void clearPiece(int piece, int tim) {
	if (hasStopped[piece])return;
	hasStopped[piece] = true;
	fori(pieces[piece].size()) {
		pii cur = pieces[piece][i];
		answer[cur.first + tim][cur.second] = true;
		pii up = cellUp[cur.first][cur.second];
		if (up == pii(0, 0))continue;
		if (hasStopped[inPiece[up.first][up.second]])continue;
		willStop[tim + cur.first - up.first - 1].push_back(inPiece[up.first][up.second]);
	}
}
// END Justas region

bool isValid(int i, int j) {
	return i >= 0 && i < N && j >= 0 && j < M;
}

void setId(int si, int sj, ll id) {
	if (ids[si][sj] != 0) return;
	ids[si][sj] = id;
	FOR(d, 0, 4) {
		int i = si + dir[d].first;
		int j = sj + dir[d].second;
		if (!isValid(i, j)) continue;
		if (!grid[i][j]) continue;
		setId(i, j, id);
	}
}

void reset(int n, int m) {
	N = n; M = m;
	groups = 1;
	pieceCount = 0;
	groupFall.clear();
	FOR(i, 0, MAX_N+100) {
		FOR(j, 0, MAX_N+100) {
			ids[i][j] = 0;
			grid[i][j] = false;
			newGrid[i][j] = false;
			inPiece[i][j] = 0;
			vis[i][j] = false;
			cellUp[i][j] = { 0,0 };
			answer[i][j] = 0;
		}
		willStop[i].clear();
		highestGroup[i] = { 0,0 };
	}
	FOR(i, 0, MAX_N*MAX_N+100) {
		pieces[i].clear();
		hasStopped[i] = false;
	}
}

string mine(int n, int m, string lines[]) {
	reset(n, m);
	groupFall.pb(0);
	FOR(i, 0, n) {
		FOR(j, 0, m) {
			char c = lines[i][j];
			grid[i][j] = (c == '#');
		}
	}

	FOR(j, 0, m) highestGroup[j] = { 0, n };

	FOR(i, 0, n) {
		FOR(j, 0, m) {
			if (grid[i][j] && ids[i][j] == 0) {
				groupFall.pb(MAX_N * 10);
				setId(i, j, groups++);
			}
		}
	}

	int changed;
	
	do {
		changed = 0;
		FOR(j, 0, m) highestGroup[j] = { 0, n };
		for (int i = n - 1; i >= 0; i--) {
			FOR(j, 0, m) {
				int id = ids[i][j];
				if (grid[i][j]) {
					int prev = groupFall[id];
					if (highestGroup[j].first == 0) {
						groupFall[id] = min(groupFall[id], (ll)(n - 1 - i));
					}
					else {
						if (highestGroup[j].first != id) {
							ll x = groupFall[highestGroup[j].first] + highestGroup[j].second - i - 1;
							groupFall[id] = min(groupFall[id], x);
						}
					}
					if (groupFall[id] != prev) changed++;
					highestGroup[j] = { ids[i][j], i };
				}
			}
		}
	} while (changed > 0);

	FOR(i, 0, n) {
		FOR(j, 0, m) {
			if (ids[i][j] == 0) continue;
			int ii = i + groupFall[ids[i][j]];
			int jj = j;
			newGrid[ii][jj] = true;
		}
	}

	ostringstream ss;

	FOR(i, 0, n) {
		FOR(j, 0, m) {
			ss << (newGrid[i][j] ? '#' : '.');
		}
		ss << endl;
	}
	return ss.str();
}

string justo(int n, int m, string lines[]) {
	reset(n, m);
	fori1(N) {
		string s = lines[i - 1];
		forj(M)grid[i][j + 1] = (s[j] == '#');

	}
	fori1(N)forj1(M) {
		if (grid[i][j] && !vis[i][j]) {
			dfs(i, j, pieceCount);
			pieceCount++;

		}

	}
	forj1(M) {
		pii up = pii(0, 0);
		fori1(N + 1) {
			cellUp[i][j] = up;
			if (grid[i][j])up = pii(i, j);

		}
	}
	forj1(M) {
		pii up = cellUp[N + 1][j];
		if (up != pii(0, 0))
			willStop[N - up.first].push_back(inPiece[up.first][up.second]);

	}
	fori(N + 2)
		forj(willStop[i].size()) {
		clearPiece(willStop[i][j], i);
	}
	ostringstream ss;
	fori1(N) {
		forj1(M) {
			if (answer[i][j])ss << '#';
			else ss << '.';
		}
		ss << "\n";
	}
	return ss.str();
}

string lines[MAX_N];

int main()
{
	FAST_IO
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	
	/*srand(time(NULL));

	FOR(T, 0, 1000) {
		int n = rand()%MAX_N+1;
		int m = rand() % MAX_N + 1;
		FOR(i, 0, n) {
			string s = "";
			FOR(j, 0, m) {
				if (rand() % 2) {
					s += "#";
				}
				else {
					s += ".";
				}
			}
			lines[i] = s;
		}
		
		string correct = justo(n, m, lines);
		string myAns = mine(n, m, lines);
		cout << "Test #" << (T + 1) << ": ";
		if (myAns != correct) {
			cout << "WA" << endl;
			cout << "Test: " << endl;
			cout << n << " " << m << endl;
			FOR(i, 0, n) cout << lines[i] << endl;
			cout << "Expected: " << endl << correct << endl << "Actual: " << endl << myAns << endl;
		}
		else {
			cout << "OK" << endl;
		}
	}*/
	int n, m;
	cin >> n >> m;
	FOR(i, 0, n) {
		cin >> lines[i];
	}
	cout << mine(n, m, lines);

	return 0;
}