CSES - HIIT Open 2019 - Results
Submission details
Task:Coloring Grids
Sender:Game of Nolife
Submission time:2019-05-25 15:47:26 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.04 sdetails
#3ACCEPTED0.02 sdetails
#4ACCEPTED0.03 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.03 sdetails
#7ACCEPTED0.03 sdetails
#8ACCEPTED0.03 sdetails
#9ACCEPTED0.03 sdetails
#100.04 sdetails
#110.03 sdetails
#12ACCEPTED0.03 sdetails
#13ACCEPTED0.15 sdetails
#14ACCEPTED0.17 sdetails
#15ACCEPTED0.16 sdetails
#16ACCEPTED0.17 sdetails
#17ACCEPTED0.07 sdetails
#18ACCEPTED0.12 sdetails
#19ACCEPTED0.16 sdetails
#20ACCEPTED0.07 sdetails
#21ACCEPTED0.04 sdetails
#22ACCEPTED0.03 sdetails
#23ACCEPTED0.04 sdetails
#24ACCEPTED0.12 sdetails
#25ACCEPTED0.03 sdetails
#26ACCEPTED0.04 sdetails
#27ACCEPTED0.04 sdetails
#28ACCEPTED0.12 sdetails
#29ACCEPTED0.04 sdetails
#30ACCEPTED0.05 sdetails
#31ACCEPTED0.05 sdetails
#32ACCEPTED0.05 sdetails
#33ACCEPTED0.04 sdetails
#34ACCEPTED0.05 sdetails
#35ACCEPTED0.03 sdetails
#36ACCEPTED0.05 sdetails
#37ACCEPTED0.04 sdetails
#38ACCEPTED0.04 sdetails
#39ACCEPTED0.05 sdetails
#40ACCEPTED0.07 sdetails
#41ACCEPTED0.04 sdetails
#42ACCEPTED0.04 sdetails
#43ACCEPTED0.04 sdetails
#44ACCEPTED0.11 sdetails
#45ACCEPTED0.09 sdetails
#46ACCEPTED0.04 sdetails
#47ACCEPTED0.04 sdetails
#48ACCEPTED0.04 sdetails
#49ACCEPTED0.10 sdetails
#50ACCEPTED0.06 sdetails
#51ACCEPTED0.06 sdetails
#52ACCEPTED0.06 sdetails
#53ACCEPTED0.05 sdetails
#54ACCEPTED0.04 sdetails
#55ACCEPTED0.04 sdetails
#56ACCEPTED0.05 sdetails
#57ACCEPTED0.04 sdetails
#58ACCEPTED0.05 sdetails
#59ACCEPTED0.04 sdetails
#60ACCEPTED0.04 sdetails
#61ACCEPTED0.05 sdetails
#62ACCEPTED0.04 sdetails
#63ACCEPTED0.04 sdetails
#64ACCEPTED0.04 sdetails
#65ACCEPTED0.05 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;

int n,m;
string og[101010], ans[101010];
vector<int> vis[101010];
vector<set<int>> pos[101010];

bool change(int i,int j) {
    set<char> posi;
    posi.insert('1');
    posi.insert('2');
    posi.insert('3');
    posi.insert('4');
    posi.erase(og[i][j]);
    for (int ii=-1;ii<=1;ii++) {
        for (int jj=-1;jj<=1;jj++) {
            if (abs(ii+jj)==1) {
                if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) posi.erase(og[i+ii][j+jj]);
            }
        }
    }
    if (posi.empty()) return false;
    char t=(*posi.begin());
    og[i][j]=t;
    return true;
}

void bfs() {
    vector<pair<pair<int,int>,pair<int,int>>> v;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (og[i][j]=='0') {
                for (int ii=-1;ii<=1;ii++) {
                    for (int jj=-1;jj<=1;jj++) {
                        if (abs(ii+jj)==1) {
                            if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) {
                                if (og[i+ii][j+jj]!='0' && !vis[i+ii][j+jj]) {
                                    vis[i+ii][j+jj]=1;
                                    v.push_back({{i+ii,j+jj},{-1,-1}});
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    for (int k=0;k<(int)v.size();k++) {
        if (change(v[k].F.F,v[k].F.S)) {
            pair<int,int> prev=v[k].S;
            for (int kk=k-1;kk>=0;kk--) {
                if (v[kk].F==prev) {
                    assert(change(v[kk].F.F,v[kk].F.S));
                    prev=v[kk].S;
                }
            }
            return;
        } else {
            int i=v[k].F.F;
            int j=v[k].F.S;
            for (int ii=-1;ii<=1;ii++) {
                for (int jj=-1;jj<=1;jj++) {
                    if (abs(ii+jj)==1) {
                        if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) {
                            if (!vis[i+ii][j+jj]) {
                                vis[i+ii][j+jj]=1;
                                v.push_back({{i+ii,j+jj},{i,j}});
                            }
                        }
                    }
                }
            }
        }
    }
}

bool solve() {
    for (int i=0;i<n;i++) {
        pos[i].clear();
        ans[i]=og[i];
        for (int j=0;j<m;j++) {
            pos[i].push_back({});
        }
    }
    priority_queue<pair<int,pair<int,int>>> pq;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (og[i][j] == '0') {
                for (int k=0;k<4;k++) pos[i][j].insert('1'+k);
                for (int ii=-1;ii<=1;ii++) {
                    for (int jj=-1;jj<=1;jj++) {
                        if (abs(ii+jj)==1) {
                            if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) pos[i][j].erase(og[i+ii][j+jj]);
                        }
                    }
                }
                pq.push({-(int)pos[i][j].size(),{i,j}});
            }
        }
    }
    while (!pq.empty()) {
        auto xx = pq.top();
 //       cerr<<xx.F<<" "<<xx.S.F<<" "<<xx.S.S<<endl;
        pq.pop();
        if (ans[xx.S.F][xx.S.S]!='0') continue;
        int i= xx.S.F;
        int j=xx.S.S;
        if (pos[i][j].size()==0) return false;
        vector<int> v;
        for (int k=0;k<4;k++) v.push_back(0);
        for (int ii=-1;ii<=1;ii++) {
            for (int jj=-1;jj<=1;jj++) {
                if (abs(ii+jj)==1) {
                    if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) {
                        if (ans[i+ii][j+jj]=='0') {
                            for (int k=0;k<4;k++) v[k]++;
                            for (char c : pos[i+ii][j+jj]) v[c-'1']--;
                        } else {
                            v[ans[i+ii][j+jj]-'1'] = -1;
                        }
                    }
                }
            }
        }
        char parsa='1';
        int maxef=-1;
        for (char c : pos[i][j]) {
//            cerr<<c<<endl;
//            cerr<<v[c-'1']<<endl;
            if (v[c-'1']>maxef) {
                maxef = v[c-'1'];
                parsa = c;
//                cerr<<i<<" "<<j<<" "<<parsa<<" "<<maxef<<endl;
            }
        }
        ans[i][j]=parsa;
        for (int ii=-1;ii<=1;ii++) {
            for (int jj=-1;jj<=1;jj++) {
                if (abs(ii+jj)==1) {
                    if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) {
                        if (ans[i+ii][j+jj]=='0' && pos[i+ii][j+jj].count(parsa)) {
                            pos[i+ii][j+jj].erase(parsa);
                            pq.push({-(int)pos[i+ii][j+jj].size(),{i+ii,j+jj}});
                        }
                    }
                }
            }
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for (int i=0;i<n;i++) {
        cin>>og[i];
        for (int j=0;j<m;j++) {
            vis[i].push_back(0);
        }
    }
    if (solve()) {
//        cerr<<"MOI"<<endl;
        for (int i=0;i<n;i++) {
            cout<<ans[i]<<"\n";
        }
        return 0;
    }
    bfs();
    solve();
    for (int i=0;i<n;i++) {
        cout<<ans[i]<<"\n";
    }
    
}

Test details

Test 1

Verdict: ACCEPTED

input
3 4
1234
2000
1234

correct output
1234
2121
1234

user output
1234
2123
1234

Test 2

Verdict: ACCEPTED

input
3 3
123
401
132

correct output
123
341
132

user output
143
421
132

Test 3

Verdict: ACCEPTED

input
4 5
14234
41001
14002
23134

correct output
14234
41321
14212
23134

user output
14234
41321
14212
23134

Test 4

Verdict: ACCEPTED

input
4 5
14214
41002
12001
23124

correct output
14214
41342
12431
23124

user output
14214
41342
12431
23124

Test 5

Verdict: ACCEPTED

input
4 5
14234
41001
14003
23134

correct output
14234
41321
14213
23134

user output
14234
41321
14213
23134

Test 6

Verdict: ACCEPTED

input
4 5
14234
41001
14303
23414

correct output
14234
41421
14343
23414

user output
14234
41421
14343
23414

Test 7

Verdict: ACCEPTED

input
20 20
14343212121212121212
30000000312121212121
12430120121212121212
21210210212121212121
...

correct output
14343212121212121212
31214341312121212121
12432123121212121212
21213214212121212121
12124123121212121212
...

user output
14343212121212121212
31214341312121212121
12432123121212121212
21213214212121212121
12124123121212121212
...

Test 8

Verdict: ACCEPTED

input
4 10
1321412123
4000000001
1200121002
2312434213

correct output
1321412123
4134243241
1243121432
2312434213

user output
1321412123
4132343241
1243121432
2312434213

Test 9

Verdict: ACCEPTED

input
4 8
14232123
41000004
14323212
23134323

correct output
14212123
41431434
14323212
23134323

user output
14132123
41241434
14323212
23134323

Test 10

Verdict:

input
5 10
4123412341
2341234123
1200000041
3412341234
...

correct output
4143412341
2321234123
1243412341
3412341234
1234123412

user output
(empty)

Error:
code: input/code.cpp:61: void bfs(): Assertion `change(v[kk].F.F,v[kk].F.S)' failed.

Test 11

Verdict:

input
5 10
4123412341
2341234123
1234012341
3412341234
...

correct output
4123212341
2341434123
1234212341
3412341234
1234123412

user output
4123412341
2341234123
4123412341
3412341234
1234123412

Test 12

Verdict: ACCEPTED

input
4 5
14234
41001
14023
23134

correct output
14214
41431
14323
23134

user output
14134
41241
14323
23134

Test 13

Verdict: ACCEPTED

input
1 100000
000000000000000000000000000000...

correct output
212121212121212121212121212121...

user output
212121212121212121212121212121...

Test 14

Verdict: ACCEPTED

input
10 10000
000000000000000000000000000000...

correct output
321212121212121212121212121212...

user output
121212121212121212121212121212...

Test 15

Verdict: ACCEPTED

input
100 1000
000000000000000000000000000000...

correct output
321212121212121212121212121212...

user output
121212121212121212121212121212...

Test 16

Verdict: ACCEPTED

input
100000 1
0
0
0
0
...

correct output
2
1
2
1
2
...

user output
2
1
2
1
2
...

Test 17

Verdict: ACCEPTED

input
5 20000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 18

Verdict: ACCEPTED

input
10 10000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 19

Verdict: ACCEPTED

input
100 1000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 20

Verdict: ACCEPTED

input
1000 100
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 21

Verdict: ACCEPTED

input
10 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13424
24131
31242
42313
13424
...

Test 22

Verdict: ACCEPTED

input
100 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13424
24131
31242
42313
13424
...

Test 23

Verdict: ACCEPTED

input
1000 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13424
24131
31242
42313
13424
...

Test 24

Verdict: ACCEPTED

input
20000 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13424
24131
31242
42313
13424
...

Test 25

Verdict: ACCEPTED

input
10 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13124
24231
31342
42413
13124
...

Test 26

Verdict: ACCEPTED

input
100 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13124
24231
31342
42413
13124
...

Test 27

Verdict: ACCEPTED

input
1000 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13124
24231
31342
42413
13124
...

Test 28

Verdict: ACCEPTED

input
20000 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13124
24231
31342
42413
13124
...

Test 29

Verdict: ACCEPTED

input
5 20000
241313234212313241423414131214...

correct output
241313234212313241423414131214...

user output
241313234212313241423414131214...

Test 30

Verdict: ACCEPTED

input
5 20000
314241242424212323134342121212...

correct output
314241242424212323134342121212...

user output
314241242424212323134342121212...

Test 31

Verdict: ACCEPTED

input
5 20000
413423124243142121312312324214...

correct output
413423124243142121312312324214...

user output
413423124243142121312312324214...

Test 32

Verdict: ACCEPTED

input
5 20000
421423243142412132313232343234...

correct output
421423243142412132313232343234...

user output
421423243142412132313232343234...

Test 33

Verdict: ACCEPTED

input
10 10000
124231243413413131241231242432...

correct output
124231243413413131241231242432...

user output
124231243413413131241231242432...

Test 34

Verdict: ACCEPTED

input
10 10000
423142321432132421242414123431...

correct output
423142321432132421242414123431...

user output
423142321432132421242414123431...

Test 35

Verdict: ACCEPTED

input
10 10000
123123132324343232321412342123...

correct output
123123132324343232321412342123...

user output
123123132324343232321412342123...

Test 36

Verdict: ACCEPTED

input
10 10000
432142131231321234131432342343...

correct output
432142131231321234131432342343...

user output
432142131231321234131432342343...

Test 37

Verdict: ACCEPTED

input
100 1000
123421343121323141432414214321...

correct output
123421343121323141432414214321...

user output
123421343121323141432414214321...

Test 38

Verdict: ACCEPTED

input
100 1000
214241423231431232124132142413...

correct output
214241423231431232124132142413...

user output
214241423231431232124132142413...

Test 39

Verdict: ACCEPTED

input
100 1000
434231312432423214312132121343...

correct output
434231312432423214312132121343...

user output
434231312432423214312132121343...

Test 40

Verdict: ACCEPTED

input
100 1000
142123213232321323241231234324...

correct output
142123213232321323241231234324...

user output
142123213232321323241231234324...

Test 41

Verdict: ACCEPTED

input
300 333
123232434313124242314324312314...

correct output
123232434313124242314324312314...

user output
123232434313124242314324312314...

Test 42

Verdict: ACCEPTED

input
300 333
234123421414242121434343124132...

correct output
234123421414242121434343124132...

user output
234123421414242121434343124132...

Test 43

Verdict: ACCEPTED

input
300 333
312321423131434121234124343131...

correct output
312321423131434121234124343131...

user output
312321423131434121234124343131...

Test 44

Verdict: ACCEPTED

input
300 333
123213421343414231434124312131...

correct output
123213421343414231434124312131...

user output
123213421343414231434124312131...

Test 45

Verdict: ACCEPTED

input
33333 3
123
204
301
402
...

correct output
123
214
321
412
123
...

user output
123
214
321
412
123
...

Test 46

Verdict: ACCEPTED

input
10 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42123
13414
...

user output
13124
24231
31342
42123
13214
...

Test 47

Verdict: ACCEPTED

input
100 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13124
24231
31342
42413
13124
...

Test 48

Verdict: ACCEPTED

input
1000 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13124
24231
31342
42413
13124
...

Test 49

Verdict: ACCEPTED

input
20000 5
13124
24231
31042
42013
...

correct output
13124
24231
31342
42413
13124
...

user output
13124
24231
31342
42413
13124
...

Test 50

Verdict: ACCEPTED

input
10 10000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 51

Verdict: ACCEPTED

input
10 10000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 52

Verdict: ACCEPTED

input
10 10000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 53

Verdict: ACCEPTED

input
10 10000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 54

Verdict: ACCEPTED

input
100 1000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 55

Verdict: ACCEPTED

input
100 1000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 56

Verdict: ACCEPTED

input
100 1000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 57

Verdict: ACCEPTED

input
100 1000
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 58

Verdict: ACCEPTED

input
300 333
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 59

Verdict: ACCEPTED

input
300 333
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 60

Verdict: ACCEPTED

input
300 333
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 61

Verdict: ACCEPTED

input
300 333
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 62

Verdict: ACCEPTED

input
1000 100
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 63

Verdict: ACCEPTED

input
1000 100
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 64

Verdict: ACCEPTED

input
1000 100
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...

Test 65

Verdict: ACCEPTED

input
1000 100
123412341234123412341234123412...

correct output
123412341234123412341234123412...

user output
123412341234123412341234123412...