CSES - HIIT Open 2019 - Results
Submission details
Task:Insert Whitespace
Sender:Lahna
Submission time:2019-05-25 14:06:35 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.03 sdetails
#3--details
#4--details
#50.02 sdetails
#60.02 sdetails
#7ACCEPTED0.02 sdetails
#8--details
#9--details
#10ACCEPTED0.02 sdetails
#11--details
#12--details
#130.02 sdetails

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 second
using 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:

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:

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:

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

correct output
    Lorem ipsum dolor sit amet...

user output
IMPOSSIBLE

Test 6

Verdict:

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:

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

correct output
    Lorem  ipsum dolor sit ame...

user output
(empty)

Test 9

Verdict:

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:

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

correct output
                              ...

user output
(empty)

Test 12

Verdict:

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:

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

correct output
                              ...

user output
IMPOSSIBLE