CSES - HIIT Open 2019 - Results
Submission details
Task:Insert Whitespace
Sender:Lahna
Submission time:2019-05-25 15:02:14 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.03 sdetails
#2ACCEPTED0.02 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#50.02 sdetails
#60.02 sdetails
#70.04 sdetails
#80.03 sdetails
#90.04 sdetails
#100.03 sdetails
#11ACCEPTED0.02 sdetails
#12ACCEPTED0.01 sdetails
#130.01 sdetails

Compiler report

input/code.cpp: In function 'void calc_can(int)':
input/code.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<words[i].size();++j){
                ~^~~~~~~~~~~~~~~~
input/code.cpp:58: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;


map<int, int> cand[5555];


void stcan(int j, int l, int e){
  if (cand[j].count(l)) return;
  cand[j][l]=e;
}

int gtcan(int j, int l){
  if (!cand[j].count(l)) cout << "QQQQQ" << endl;
  return cand[j][l];
}

int mncan(int j){
  if (!cand[j].size()) return -1222333444;
  auto w=cand[j].begin();
  return w->F;
}
int mxcan(int j){
  if (!cand[j].size()) return 1222333444;
  auto w=cand[j].end();--w;
  return w->F;
}

void calc_can(int i){
  for (int j=0;j<5555;++j)cand[j].clear();
  stcan(0, 0, 0);
  for (int j=0;j<words[i].size();++j){
    if (!cand[j].size()) continue;
    int noch=words[i][j].size();
    
    if (noch==w){
      for (auto w:cand[j]){
        stcan(j+1, w.F+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){
        for (auto w:cand[j]){
          stcan(k+1, w.F+1, j);
        }
      }
      if (noch>w) break;
    }
    if (noch<=w){
      for (auto w:cand[j]){
        stcan(words[i].size(), w.F+1, j);
      }
    }
  }
}

void mkline(int i, int a, int b, vector<string>& lines){
//   cout << "mkline " << i << " " << a << " " << b << endl;
  int noch=-1;
  for (int j=a;j<b;++j){
    noch+=words[i][j].size()+1;
  }
//   cout << noch << endl;
  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];
  }
//   cout << dd << endl;
}

void get_lines(int i, int nol, vector<string>& lines){
//   cout << "get_lines" << i << " " << nol << endl;
  calc_can(i);
  int c=words[i].size();
  while (c){
    int w=gtcan(c, nol);
    mkline(i, w, c, lines);
    c=w;
    --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<2 || 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]=mncan(words[i].size());
    mxlines[i]=mxcan(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
...
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: 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
...
Truncated

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:

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

correct output
IMPOSSIBLE

user output
(empty)

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

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

Test 10

Verdict:

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

correct output
IMPOSSIBLE

user output
(empty)

Test 11

Verdict: ACCEPTED

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

correct output
                              ...

user output
                              ...
Truncated

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

Test 13

Verdict:

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

correct output
                              ...

user output
IMPOSSIBLE