CSES - Putka Open 2020 – 4/5

CSES - Putka Open 2020 – 4/5 - Results

Submission details
Task:	Ruudukko
Sender:	Lieska
Submission time:	2020-11-08 19:49:44 +0200
Language:	C++ (C++11)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	RUNTIME ERROR	0
#2	WRONG ANSWER	0
#3	RUNTIME ERROR	0
#4	WRONG ANSWER	0
#5	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	RUNTIME ERROR	0.01 s	1, 5	details
#2	WRONG ANSWER	0.01 s	2, 5	details
#3	RUNTIME ERROR	0.02 s	3, 5	details
#4	WRONG ANSWER	0.36 s	4, 5	details
#5	TIME LIMIT EXCEEDED	--	5	details
#6	TIME LIMIT EXCEEDED	--	5	details
#7	WRONG ANSWER	0.01 s	2, 5	details
#8	WRONG ANSWER	0.01 s	2, 5	details
#9	WRONG ANSWER	0.01 s	3, 5	details
#10	WRONG ANSWER	0.01 s	3, 5	details
#11	WRONG ANSWER	0.03 s	3, 5	details
#12	RUNTIME ERROR	0.01 s	3, 5	details
#13	WRONG ANSWER	0.01 s	4, 5	details
#14	TIME LIMIT EXCEEDED	--	5	details
#15	WRONG ANSWER	0.01 s	3, 5	details
#16	TIME LIMIT EXCEEDED	--	5	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:132:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<v.size(); ++i){
                       ~^~~~~~~~~
input/code.cpp:145:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (i!=(v.size()-1)){
                     ~^~~~~~~~~~~~~~
input/code.cpp:203:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (a<v.size() && v[a]==(v[a-1]+1)) a++;
                ~^~~~~~~~~
input/code.cpp:204:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (a!=v.size() && v[a]<=x2){
             ~^~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;

#define PB push_back

int yes=0, t[3030], valmis;
vector<int> ans[3030], r[3030];

void poista(int a, int b){
    int c=ans[a][0], d=ans[a][1];
    ans[a].pop_back();
    ans[a].pop_back();
    if (c!=b) ans[a].PB(c);
    else ans[a].PB(d);

    c=ans[b][0], d=ans[b][1];
    ans[b].pop_back();
    ans[b].pop_back();
    if (c!=a) ans[b].PB(c);
    else ans[b].PB(d);
}

void lisaa2(int a, int b){
    ans[a].PB(b);
    ans[b].PB(a);
}

void lisaa4(int a, int b, int c, int d){
    lisaa2(a, b);
    lisaa2(b, c);
    lisaa2(c, d);
}

void lisaa6(int a, int b, int c, int d, int e, int f){
    lisaa4(a, b, c, d);
    lisaa2(d, e);
    lisaa2(e, f);
}

void lisaa8(int a, int b, int c, int d, int e, int f, int g, int h){
    lisaa6(a, b, c, d, e, f);
    lisaa2(f, g);
    lisaa2(g, h);
}

void lisaa10(int a, int b, int c, int d, int e, int f, int g, int h, int i, int j){
    lisaa8(a, b, c, d, e, f, g, h);
    lisaa2(h, i);
    lisaa2(i, j);
}

void f(int a, int edel, int k){
    //cout << a << " " << edel << " " << k << " " << valmis <<  "\n";
    if (yes) return;
    if (t[a]==-1){
        if (k==valmis) {
            ans[edel].PB(a);
            ans[a].PB(edel);
            yes=1;
        }
        return;
    }
    if (t[a] || yes) return;
    t[a]=1;
    ans[edel].PB(a);
    ans[a].PB(edel);
    for (auto u:r[a]){
        if (u!=edel){
            f(u, a, k+1);
        }
    }
    if (yes==0){
        ans[edel].pop_back();
        ans[a].pop_back();
    }
    t[a]=0;
    return;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t10;
    cin >> t10;
    for (int i1=1; i1<=t10; ++i1){
        int n, m;
        cin >> n >> m;
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        for (int i=0; i<=n*m; ++i){
            while (r[i].size()) r[i].pop_back();
        }
        for (int i=1; i<=n*m; ++i) t[i]=0;
        for (int i=0; i<=n*m; ++i){
            while (ans[i].size()) ans[i].pop_back();
        }
        int kaanto=0;
        if (x2<x1){
            swap(x2, x1);
            swap(y1, y2);
            kaanto=1;
        }
        set<int> s;
        s.insert(x1);
        if (x1>1){
            s.insert(x1-1);
            if ((x1-1)%2==0) s.insert(x1-2);
        }
        if (x2>x1){
            s.insert(x2);
            if ((x2-x1)>1){
                s.insert(x1+1);
                if ((x2-x1)%2==1) s.insert(x1+2);
            }
        }
        if (x2<m){
            s.insert(x2+1);
            if ((m-x2)%2==0) s.insert(x2+2);
        }
        while (s.size()<7){
            int a=1;
            while (s.count(a)==1) a++;
            if (a<m){
                s.insert(a);
                s.insert(a+1);
            }
            else break;
        }
        vector<int> v;
        for (auto u:s) v.PB(u);
        for (int i=0; i<v.size(); ++i){
            //cout << i << " " << v[i] << " hei\n";
            for (int j=1; j<=n; ++j){
                int a=(j-1)*m + v[i];
                if (j!=1){
                    r[a].PB((j-2)*m + v[i]);
                }
                if (j!=n){
                    r[a].PB(j*m + v[i]);
                }
                if (i!=0){
                    r[a].PB((j-1)*m + v[i-1]);
                }
                if (i!=(v.size()-1)){
                    r[a].PB((j-1)*m + v[i+1]);
                }
            }
        }
        valmis=v.size()*n;
        /*
        for (int i=1; i<=n; ++i){
            for (int j=1; j<=m; ++j){
                for (auto u:r[(i-1)*m+j]) cout << i << " " << j << " " << u << "\n";
            }
        }
        */
        t[(y2-1)*m + x2]=-1;
        yes=0;
        f((y1-1)*m+x1, 0, 1);
        if (yes==0){
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
        /*
        for (int i=1; i<=n; ++i){
            for (int j=1; j<=m; ++j){
                for (auto u:ans[(i-1)*m+j]) cout << i << " " << j << " " << u << "\n";
            }
        }
        */

        if (n>1){
            for (int i=v[0]; i>=3; i-=2){
                poista(i, i+m);
                if (n==2){
                    lisaa6(i, i-1, i-2, i-2+m, i-1+m, i+m);
                }
                if (n==3){
                    lisaa8(i, i-1, i-2, i-2+m, i-2+2*m, i-1+2*m, i-1+m, i+m);
                }
                if (n==4){
                    lisaa10(i, i-1, i-2, i-2+m, i-2+2*m, i-2+3*m, i-1+3*m, i-1+2*m, i-1+m, i+m);
                }
            }

            for (int i=v[v.size()-1]; i<=m-2; i+=2){
                poista(i, i+m);
                if (n==2){
                    lisaa6(i, i+1, i+2, i+2+m, i+1+m, i+m);
                }
                if (n==3){
                    lisaa8(i, i+1, i+2, i+2+m, i+2+2*m, i+1+2*m, i+1+m, i+m);
                }
                if (n==4){
                    lisaa10(i, i+1, i+2, i+2+m, i+2+2*m, i+2+3*m, i+1+3*m, i+1+2*m, i+1+m, i+m);
                }
            }
        }
        int a=0;
        while (v[a]<=x1) a++;
        while (a<v.size() && v[a]==(v[a-1]+1)) a++;
        if (a!=v.size() && v[a]<=x2){
            for (int i=v[a-1]; i<=v[a]-3; i+=2){
                if (n==1){
                    poista(i, v[a]);
                    lisaa4(i, i+1, i+2, v[a]);
                }
                if (n==2){
                    if (ans[i][0]==v[a] || ans[i][1]==v[a]){
                        poista(i, v[a]);
                        lisaa6(i, i+1, i+1+m, i+2+m, i+2, v[a]);
                    }
                    else{
                        poista(i+m, v[a]+m);
                        lisaa6(i+m, i+1+m, i+1, i+2, i+2+m, v[a]+m);
                    }
                }
                if (n==3){
                    if (ans[i+m][0]==(v[a]+m) || ans[i+m][1]==(v[a]+m)){
                        poista(i, v[a]);
                        lisaa4(i, i+1, i+2, v[a]);
                        poista(i+m, v[a]+m);
                        lisaa4(i+m, i+1+m, i+2+m, v[a]+m);
                        poista(i+2*m, v[a]+2*m);
                        lisaa4(i+2*m, i+1+2*m, i+2+2*m, v[a]+2*m);
                    }
                    else{
                        if (ans[i][0]==v[a] || ans[i][1]==v[a]){
                            poista(i, v[a]);
                            lisaa8(i, i+1, i+1+m, i+1+2*m, i+2+2*m, i+2+m, i+2, v[a]);
                        }
                        else{
                            poista(i+2*m, v[a]+2*m);
                            lisaa8(i+2*m, i+1+2*m, i+1+m, i+1, i+2, i+2+m, i+2+2*m, v[a]+2*m);
                        }
                    }
                }
            }
        }

        a=(y1-1)*m+x1;
        int edel=0;
        if (kaanto==0){
            while (true){
                int b=0;
                if (ans[a][0]!=edel) b=ans[a][0];
                else b=ans[a][1];
                if (b==(a+1)) cout << 'R';
                if (b==(a-1)) cout << 'L';
                if (b==(a+m)) cout << 'D';
                if (b==(a-m)) cout << 'U';
                if (b==(y2-1)*m+x2) break;
                edel=a;
                a=b;
            }
        }
        else{
            while (true){
                int b=0;
                if (ans[a][0]!=edel) b=ans[a][0];
                else b=ans[a][1];
                if (b==(a+1)) cout << 'L';
                if (b==(a-1)) cout << 'R';
                if (b==(a+m)) cout << 'U';
                if (b==(a-m)) cout << 'D';
                if (b==(y2-1)*m+x2) break;
                edel=a;
                a=b;
            }
        }
        cout << "\n";
    }
}

Test details

Test 1

Group: 1, 5

Verdict: RUNTIME ERROR

input
`100 1 45 1 45 1 1 1 18 1 1 1 10 1 47 1 17 1 30 1 33 1 28 1 20 ...` view save

correct output
`YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...` view save

user output
(empty)

Error:

double free or corruption (out)

Test 2

Group: 2, 5

Verdict: WRONG ANSWER

input
`100 2 43 1 33 1 21 2 2 1 1 2 2 2 32 1 1 2 8 2 14 1 12 1 14 ...` view save

correct output
`NO NO NO NO YES ...` view save

user output
`NO NO NO NO YES ...` Truncated

Test 3

Group: 3, 5

Verdict: RUNTIME ERROR

input
`100 3 4 2 1 2 4 3 38 2 24 1 22 3 29 2 23 2 3 3 8 3 1 1 2 ...` view save

correct output
`NO NO NO YES RRRRRRRUULDLULDLULDLLUR ...` view save

user output
(empty)

Error:

free(): invalid next size (fast)

Test 4

Group: 4, 5

Verdict: WRONG ANSWER

input
`100 4 25 2 19 1 5 4 13 3 10 4 12 4 7 3 1 4 2 4 23 1 19 2 5 ...` view save

correct output
`YES DDRRRRRRULLLLLURRRRRULLLLLLLDD...` view save

user output
`YES UURDDRRRUUULDDLUULLLDDDLLLLLLU...` Truncated

Test 5

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100 16 8 13 1 14 8 41 21 19 11 32 12 46 17 13 7 6 11 8 41 4 32 4 12 ...` view save

correct output
`NO YES LURULURULURULURULURRDDDDDDDDDR...` view save

user output
(empty)

Test 6

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100 31 38 18 35 31 37 35 48 7 13 21 21 46 21 25 2 4 19 35 2 13 2 35 1 ...` view save

correct output
`YES LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...` view save

user output
(empty)

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

input
`100 2 4 1 3 1 4 2 4 2 2 1 1 2 4 2 3 1 2 2 4 2 3 1 4 ...` view save

correct output
`YES LLDRRRU NO NO NO ...` view save

user output
`YES LLDRRRU NO NO NO ...` Truncated

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

input
`100 2 5 1 2 2 4 2 5 1 2 1 1 2 5 2 1 1 2 2 5 1 1 1 5 ...` view save

correct output
`YES LDRRURRDL YES RRRDLLLLU NO ...` view save

user output
`YES LDRRURRDL YES ULLLLDRRR NO ...` Truncated

Test 9

Group: 3, 5

Verdict: WRONG ANSWER

input
`100 3 4 1 1 2 3 3 4 2 4 3 2 3 4 2 1 3 1 3 4 1 4 3 4 ...` view save

correct output
`YES DDRRRUULLDR NO YES URRRDDLULDL ...` view save

user output
`YES DDRUURRDDLU NO YES URDRURDDLLL ...` Truncated

Test 10

Group: 3, 5

Verdict: WRONG ANSWER

input
`100 3 5 3 4 3 2 3 5 3 5 2 3 3 5 3 1 2 2 3 5 3 1 3 2 ...` view save

correct output
`NO NO YES UURRRRDDLULDLU NO ...` view save

user output
`NO NO YES UURRDRURDDLLLU NO ...` Truncated

Test 11

Group: 3, 5

Verdict: WRONG ANSWER

input
`100 3 8 2 8 1 2 3 8 2 4 1 7 3 8 3 4 2 7 3 8 2 5 3 1 ...` view save

correct output
`NO NO NO YES LLLDRRRRURDRUULLLLLLLDD ...` view save

user output
`NO NO NO YES DDLUULDDLUULLDLULDDRRRU ...` Truncated

Test 12

Group: 3, 5

Verdict: RUNTIME ERROR

input
`100 3 9 1 3 2 9 3 9 1 6 1 5 3 9 3 6 2 8 3 9 3 2 3 4 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
(empty)

Error:

free(): invalid next size (fast)

Test 13

Group: 4, 5

Verdict: WRONG ANSWER

input
`100 4 4 2 2 1 4 4 4 4 1 2 2 4 4 2 1 4 3 4 4 3 1 3 3 ...` view save

correct output
`YES DDLUUURRDDDRUUU YES UUURRRDLDRDLLUU NO ...` view save

user output
`YES ULDDDRURDRUULUR YES UUURRRDDDLLURUL NO ...` Truncated

Test 14

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100 12 27 6 22 1 8 6 25 3 2 4 4 6 16 4 6 5 2 36 33 8 6 1 6 ...` view save

correct output
`YES DLDDDDDRUUUURDDDDRUURDDRRULURU...` view save

user output
(empty)

Test 15

Group: 3, 5

Verdict: WRONG ANSWER

input
`100 3 12 3 5 1 4 3 20 3 19 2 19 3 34 3 9 2 9 3 38 2 15 3 15 ...` view save

correct output
`YES RRRRRRRUULDLULDLULDLULDLDLULDL...` view save

user output
`YES RURDRUULLLDLDLULDLLLLLUURDRURD...` Truncated

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100 50 50 29 1 16 21 50 50 37 5 23 48 50 50 32 22 45 24 50 50 6 28 12 37 ...` view save

correct output
`YES DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...` view save

user output
(empty)

Putka Open 2020 – 4/5

Ruudukko

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (Lieska)