CSES - HIIT Open 2019 - Results
Submission details
Task:Insert Whitespace
Sender:Game of Nolife
Submission time:2019-05-25 13:36:21 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.03 sdetails
#4ACCEPTED0.02 sdetails
#5ACCEPTED0.03 sdetails
#6ACCEPTED0.02 sdetails
#7ACCEPTED0.03 sdetails
#8ACCEPTED0.11 sdetails
#9ACCEPTED0.11 sdetails
#10ACCEPTED0.09 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.03 sdetails
#13ACCEPTED0.02 sdetails

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

pair<int, int> dp[5005][52][82];

int n,h,w,p;
int tw=0;

string www[5005];
int par[5005];

string spas(int x){
    string r;
    for (int i=0;i<x;i++){
        r+=' ';
    }
    return r;
}

pair<pair<int, int>, string> ns(int i, int l, int ch, int sp){
    if (i==tw-1){ // kaikki loppu
        if (l==0) return {{-1, -1}, ""};
        if (ch+(int)www[i].size()<=w){
            return {{l, ch+(int)www[i].size()}, www[i]};
        } else {
            return {{-1, -1}, ""};
        }
    } else if (par[i] != par[i+1]) { // paragraph loppu
        if (l==0) return {{-1, -1}, ""};
        if (l==h-2) return {{-1, -1}, ""};
        if (ch+(int)www[i].size()<=w){
            if (l==h-1){
                return {{0, p}, www[i]+"\n#\n"+spas(p)};
            } else{
                return {{l+1, p}, www[i]+"\n"+spas(p)};
            }
        }
    } else if (ch+(int)www[i].size()==w){ // rivi loppu
        if (l==h-1){
            return {{0, 0}, www[i]+"\n#\n"};
        } else {
            return {{l+1, 0}, www[i]+"\n"};
        }
    } else if (ch+sp+(int)www[i].size()<w) { // rivi ei lopu
        return {{l, ch+sp+(int)www[i].size()}, www[i]+spas(sp)};
    } else {
        return {{-1, -1}, ""};
    }
    return {{-1, -1}, ""};
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>h>>w>>p;
    string temp;
    getline(cin, temp);
    for (int i=0;i<n;i++){
        getline(cin, temp);
        stringstream ss;
        ss<<temp;
        while (ss>>temp){
            par[tw]=i;
            www[tw++]=temp;
        }
    }
    for (int i=0;i<=tw;i++){
        for (int j=0;j<=h;j++){
            for (int k=0;k<=w;k++){
                dp[i][j][k]={-1, -1};
            }
        }
    }
    const pair<int, int> fail={-1, -1};
    dp[0][0][p]={0, 0};
    for (int i=0;i<tw;i++){
        for (int j=0;j<h;j++){
            for (int x=0;x<=w;x++){
                if (dp[i][j][x]==fail) continue;
                for (int a=1;a<=2;a++){
                    auto ne=ns(i, j, x, a);
                    if (ne.F==fail) continue;
                    dp[i+1][ne.F.F][ne.F.S]={j, x};
                }
            }
        }
    }
    pair<int, int> rec=fail;
    for (int j=0;j<h;j++){
        for (int x=0;x<=w;x++){
            if (dp[tw][j][x]!=fail) {
                rec={j, x};
            }
        }
    }
    if (rec==fail){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    vector<string> ans;
    for (int i=tw;i>0;i--){
        auto from=dp[i][rec.F][rec.S];
        int f=0;
        for (int a=1;a<=2;a++){
            auto lol=ns(i-1, from.F, from.S, a);
            if (lol.F==rec){
                ans.push_back(lol.S);
                rec=from;
                f=1;
                break;
            }
        }
        assert(f);
    }
    cout<<spas(p);
    for (int i=(int)ans.size()-1;i>=0;i--){
        cout<<ans[i];
    }
}

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

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

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

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

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

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

correct output
                              ...

user output
                              ...
Truncated