Task: | Insert Whitespace |
Sender: | Lahna |
Submission time: | 2019-05-25 14:06:35 +0300 |
Language: | C++ |
Status: | READY |
Result: | TIME LIMIT EXCEEDED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.02 s | details |
#2 | ACCEPTED | 0.03 s | details |
#3 | TIME LIMIT EXCEEDED | -- | details |
#4 | TIME LIMIT EXCEEDED | -- | details |
#5 | WRONG ANSWER | 0.02 s | details |
#6 | WRONG ANSWER | 0.02 s | details |
#7 | ACCEPTED | 0.02 s | details |
#8 | TIME LIMIT EXCEEDED | -- | details |
#9 | TIME LIMIT EXCEEDED | -- | details |
#10 | ACCEPTED | 0.02 s | details |
#11 | TIME LIMIT EXCEEDED | -- | details |
#12 | TIME LIMIT EXCEEDED | -- | details |
#13 | WRONG ANSWER | 0.02 s | details |
Compiler report
input/code.cpp: In function 'void calc_can(int)': input/code.cpp:23:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j=0;j<words[i].size()+1;++j){ ~^~~~~~~~~~~~~~~~~~ input/code.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j=0;j<words[i].size();++j){ ~^~~~~~~~~~~~~~~~ input/code.cpp:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int k=j+1;k<words[i].size();++k){ ~^~~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h>#define F first#define S secondusing namespace std;int n, h, w, p;string pg[5555];vector<string> words[5555];int mnlines[5555];int mxlines[5555];int cann[5555];int canx[5555];int enx[5555];int enn[5555];bool IMPOSSIBLE=0;void calc_can(int i){for (int j=0;j<words[i].size()+1;++j){cann[j]=1222333444;canx[j]=-122333444;}cann[0]=0;canx[0]=0;for (int j=0;j<words[i].size();++j){if (canx[j]<cann[j]) continue;int noch=words[i][j].size();if (noch==w){if (cann[j]+1<cann[j+1]){cann[j+1]=cann[j]+1;enn[j+1]=j;}if (canx[j]+1>canx[j+1]){canx[j+1]=canx[j]+1;enx[j+1]=j;}}for (int k=j+1;k<words[i].size();++k){noch+=words[i][k].size()+1;if (noch<=w && w-noch<=k-j){if (cann[j]+1<cann[k+1]){cann[k+1]=cann[j]+1;enn[k+1]=j;}if (canx[j]+1>canx[k+1]){canx[k+1]=canx[j]+1;enx[k+1]=j;}}if (noch>w) break;}if (noch<=w){if (cann[j]+1<cann[words[i].size()]){cann[words[i].size()]=cann[j]+1;enn[words[i].size()]=j;}if (canx[j]+1>canx[words[i].size()]){canx[words[i].size()]=canx[j]+1;enx[words[i].size()]=j;}}}}void mkline(int i, int a, int b, vector<string>& lines){int noch=-1;for (int j=a;j<b;++j){noch+=words[i][j].size()+1;}int dd=w-noch;lines.push_back(words[i][a]);for (int j=a+1;j<b;++j){if (dd) lines.back().push_back(' '), --dd;lines.back().push_back(' ');lines.back()+=words[i][j];}}void get_lines(int i, int nol, vector<string>& lines){calc_can(i);int c=words[i].size();while (c){if (canx[c]>nol){mkline(i, enn[c], c, lines);c=enn[c];}else{mkline(i, enx[c], c, lines);c=enx[c];}--nol;}}int tn[5555];int tx[5555];vector<pair<int, int> > possible_mod[5555];int mod[5555];void mk_page_breaks(){possible_mod[0].push_back({0,0});for (int i=0;i<n;++i){for (int j=0;j<5555;++j) mod[j]=0;for (int j=mnlines[i];j<=mxlines[i];++j){for (auto w:possible_mod[i]){bool br=0;int t=w.second+j;if (t>=h) br=1, t%=h;if (br && t!=0 && (t<1 || h-w.second<2)) continue;if (mod[t]) continue;mod[t]=1;possible_mod[i+1].push_back({t, j});}}}}int main(){cin >> n >> h >> w >> p;string s;getline(cin, s);for (int i=0;i<n;++i){getline(cin, pg[i]);string t;for (int i=0;i<p;++i)t+=" ";for (auto c:pg[i]){if (c==' ' || c=='\n'){words[i].push_back(t);t="";}else t.push_back(c);}if (t.size()) words[i].push_back(t);calc_can(i);if (canx[words[i].size()]<cann[words[i].size()]){IMPOSSIBLE=1;}mnlines[i]=cann[words[i].size()];mxlines[i]=canx[words[i].size()];}mk_page_breaks();if (possible_mod[n].size()==0) {IMPOSSIBLE=1;}if (IMPOSSIBLE) {cout << "IMPOSSIBLE\n";}else{int cp=n;int mod=possible_mod[n][0].F;vector<string> lines;while (cp){for (auto t : possible_mod[cp]){if (t.F==mod){get_lines(--cp, t.S, lines);mod-=t.S;mod%=h;if (mod<0) mod+=h;break;}}}int cl=0;for (int i=lines.size()-1;i>=0;--i,++cl){if (cl==h){cout << "#\n";cl=0;}cout << lines[i] << "\n";}}}
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 ... Truncated |
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: TIME LIMIT EXCEEDED
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 |
---|
(empty) |
Test 4
Verdict: TIME LIMIT EXCEEDED
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 |
---|
(empty) |
Test 5
Verdict: WRONG ANSWER
input |
---|
5 10 80 4 Lorem ipsum dolor sit amet, co... |
correct output |
---|
Lorem ipsum dolor sit amet... |
user output |
---|
IMPOSSIBLE |
Test 6
Verdict: WRONG ANSWER
input |
---|
5 10 70 4 Lorem ipsum dolor sit amet, co... |
correct output |
---|
Lorem ipsum dolor sit amet... |
user output |
---|
IMPOSSIBLE |
Test 7
Verdict: ACCEPTED
input |
---|
5 10 60 4 Lorem ipsum dolor sit amet, co... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 8
Verdict: TIME LIMIT EXCEEDED
input |
---|
55 20 80 4 Lorem ipsum dolor sit amet, co... |
correct output |
---|
Lorem ipsum dolor sit ame... |
user output |
---|
(empty) |
Test 9
Verdict: TIME LIMIT EXCEEDED
input |
---|
55 20 80 6 Lorem ipsum dolor sit amet, co... |
correct output |
---|
Lorem ipsum dolor sit... |
user output |
---|
(empty) |
Test 10
Verdict: ACCEPTED
input |
---|
55 20 80 8 Lorem ipsum dolor sit amet, co... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 11
Verdict: TIME LIMIT EXCEEDED
input |
---|
3 43 37 34 aaa aaaaa aaaa a aa aa aa aaa ... |
correct output |
---|
... |
user output |
---|
(empty) |
Test 12
Verdict: TIME LIMIT EXCEEDED
input |
---|
4 50 73 12 aaaaa aa a aaa a aaa aaaa aaaa... |
correct output |
---|
aaaaa aa a aaa ... |
user output |
---|
(empty) |
Test 13
Verdict: WRONG ANSWER
input |
---|
4 6 62 31 aa aaa aaa aa aaaaa aaa aaaaa ... |
correct output |
---|
... |
user output |
---|
IMPOSSIBLE |