CSES - HIIT Open 2019 - Results
Submission details
Task:Insert Whitespace
Sender:bigint bugaa
Submission time:2019-05-25 14:53:17 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.02 sdetails
#3ACCEPTED0.03 sdetails
#4ACCEPTED0.02 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.03 sdetails
#7ACCEPTED0.03 sdetails
#8ACCEPTED0.14 sdetails
#9ACCEPTED0.13 sdetails
#10ACCEPTED0.10 sdetails
#11ACCEPTED0.03 sdetails
#12ACCEPTED0.05 sdetails
#13ACCEPTED0.03 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int WC = 5001;
bool sonc[WC];
int wl[WC];
pair<int, int> dpref[50][80][WC];
int dp[50][80][WC];
struct LP {
	char t[50][80];
	LP() {
		for (int i = 0; i < 50; ++i) {
			for (int j = 0; j < 80; ++j) t[i][j] = 0;
		}
	}
	void serialize() {
		for (int i = 0; i < 50; ++i) {
			string cr;
			bool ffc = 0;
			for (int j = 80-1; j >= 0; --j) {
				if (t[i][j] == 0) {
					if (ffc) cr.push_back(' ');
				} else {
					ffc = 1;
					cr.push_back(t[i][j]);
				}
			}
			reverse(cr.begin(), cr.end());
			if (cr.size() == 0) break;
			cout << cr << "\n";
		}
	}
};
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, h, w, p;
	cin >> n >> h >> w >> p;
	vector<string> wdc;
	string tmp;
	getline(cin, tmp);
	for (int i = 0; i < n; ++i) {
		string ln;
		getline(cin, ln);
		string gs(p, ' ');
		sonc[wdc.size()] = 1;
		for (char c : ln) {
			if (c == ' ') {
				wl[wdc.size()] = gs.size();
				wdc.push_back(gs);
				gs = "";
			} else gs.push_back(c);
		}
		wl[wdc.size()] = gs.size();
		wdc.push_back(gs);
	}
	int wc = wdc.size();
	int solx = -1, soly = -1;
	dp[0][wl[0]-1][0] = 1;
	for (int i = 1; i < wc; ++i) {
		for (int x = 0; x < h; ++x) {
			if (sonc[i] && x == h-1) continue;
			if ((i+1 >= wc || sonc[i+1]) && x == 0) continue;
			for (int y = 0; y < w; ++y) {
				if (y+1 < wl[i]) {}
				else if (sonc[i]) {
					if (wl[i] != y+1) continue;
					int refr = x == 0 ? h-1 : x-1;
					for (int u = 0; u < w; ++u) {
						if (dp[refr][u][i-1]) {
							dp[x][y][i] = 1;
							dpref[x][y][i] = {refr, u};
							break;
						}
					}
				} else {
					if (y-wl[i]-1 >= 0 && dp[x][y-wl[i]-1][i-1]) {
						dp[x][y][i] = 1;
						dpref[x][y][i] = {x, y-wl[i]-1};
					}
					if (y-wl[i]-2 >= 0 && dp[x][y-wl[i]-2][i-1]) {
						dp[x][y][i] = 1;
						dpref[x][y][i] = {x, y-wl[i]-2};
					}
					if (wl[i] == y+1) {
						if (x == 0) {
							if (dp[h-1][w-1][i-1]) {
								dp[x][y][i] = 1;
								dpref[x][y][i] = {h-1, w-1};
							}
						} else {
							if (dp[x-1][w-1][i-1]) {
								dp[x][y][i] = 1;
								dpref[x][y][i] = {x-1, w-1};
							}
						}
					}
				}
				if (i == wc-1 && dp[x][y][i]) solx = x, soly = y;
			}
		}

	}
	if (solx == -1) {
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	vector<LP> fp(1);
	for (int i = wc-1; i >= 0; --i) {
		for (int ci = 0; ci < wl[i]; ci++) {
			fp.back().t[solx][soly-wl[i]+1+ci] = wdc[i][ci];
		}
		if (i == 0) break;
		int nsolx = dpref[solx][soly][i].first, nsoly = dpref[solx][soly][i].second;
		if (nsolx > solx) fp.emplace_back();
		solx = nsolx;
		soly = nsoly;
	}
	reverse(fp.begin(), fp.end());
	bool ff = 0;
	for (auto &op : fp) {
		if (ff) cout << "#\n";
		ff = 1;
		op.serialize();
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
3 5 10 2
a a a a a a a a a a a a a a a ...

correct output
  a  a a a
a  a a a a
a  a a a a
a  a a a a
a
...

user output
  a a a  a
a a a a  a
a a a a  a
a a a a  a
a
...

Test 2

Verdict: ACCEPTED

input
3 6 10 2
a a a a a a a a a a a a a a a ...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 3

Verdict: ACCEPTED

input
3 7 10 2
a a a a a a a a a a a a a a a ...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 4

Verdict: ACCEPTED

input
3 8 10 2
a a a a a a a a a a a a a a a ...

correct output
  a  a a a
a  a a a a
a  a a a a
a  a a a a
a
...

user output
  a a a  a
a a a a  a
a a a a  a
a a a a  a
a
...

Test 5

Verdict: ACCEPTED

input
5 10 80 4
Lorem ipsum dolor sit amet, co...

correct output
    Lorem ipsum dolor sit amet...

user output
    Lorem ipsum dolor sit amet...

Test 6

Verdict: ACCEPTED

input
5 10 70 4
Lorem ipsum dolor sit amet, co...

correct output
    Lorem ipsum dolor sit amet...

user output
    Lorem ipsum dolor sit amet...

Test 7

Verdict: ACCEPTED

input
5 10 60 4
Lorem ipsum dolor sit amet, co...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 8

Verdict: ACCEPTED

input
55 20 80 4
Lorem ipsum dolor sit amet, co...

correct output
    Lorem  ipsum dolor sit ame...

user output
    Lorem ipsum dolor sit amet...

Test 9

Verdict: ACCEPTED

input
55 20 80 6
Lorem ipsum dolor sit amet, co...

correct output
      Lorem  ipsum  dolor  sit...

user output
      Lorem ipsum dolor sit  a...

Test 10

Verdict: ACCEPTED

input
55 20 80 8
Lorem ipsum dolor sit amet, co...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 11

Verdict: ACCEPTED

input
3 43 37 34
aaa aaaaa aaaa a aa aa aa aaa ...

correct output
                              ...

user output
                              ...

Test 12

Verdict: ACCEPTED

input
4 50 73 12
aaaaa aa a aaa a aaa aaaa aaaa...

correct output
            aaaaa  aa  a  aaa ...

user output
            aaaaa aa a aaa a a...

Test 13

Verdict: ACCEPTED

input
4 6 62 31
aa aaa aaa aa aaaaa aaa aaaaa ...

correct output
                              ...

user output
                              ...