CSES - HIIT Open 2019 - Results
Submission details
Task:Insert Whitespace
Sender:Lahna
Submission time:2019-05-25 14:17:36
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.02 sdetails
#30.02 sdetails
#4ACCEPTED0.02 sdetails
#50.02 sdetails
#60.02 sdetails
#7ACCEPTED0.01 sdetails
#80.03 sdetails
#90.03 sdetails
#10ACCEPTED0.02 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.02 sdetails
#130.03 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.F+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()];
    
//     cout << "mn " << i << " " << mnlines[i] << endl;
//     cout << "mx " << i << " " << mxlines[i] << endl;
  }
  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
...

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
  a  a a a
a  a  a  a
a  a  a  a
a  a  a  a
a  a  a  a
...

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:

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
    Lorem  ipsum  dolor  sit  ...

Test 9

Verdict:

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

correct output
      Lorem  ipsum  dolor  sit...

user output
      Lorem  ipsum  dolor  sit...

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 ...

Test 13

Verdict:

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

correct output
                              ...

user output
IMPOSSIBLE