CSES - Putka Open 2020 – 4/5

CSES - Putka Open 2020 – 4/5 - Results

Submission details
Task:	Ruudukko
Sender:	Lieska
Submission time:	2020-11-08 22:13:03 +0200
Language:	C++ (C++11)
Status:	READY
Result:	5

Feedback
group	verdict	score
#1	ACCEPTED	5
#2	TIME LIMIT EXCEEDED	0
#3	TIME LIMIT EXCEEDED	0
#4	TIME LIMIT EXCEEDED	0
#5	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 5	details
#2	TIME LIMIT EXCEEDED	--	2, 5	details
#3	TIME LIMIT EXCEEDED	--	3, 5	details
#4	TIME LIMIT EXCEEDED	--	4, 5	details
#5	TIME LIMIT EXCEEDED	--	5	details
#6	TIME LIMIT EXCEEDED	--	5	details
#7	TIME LIMIT EXCEEDED	--	2, 5	details
#8	TIME LIMIT EXCEEDED	--	2, 5	details
#9	TIME LIMIT EXCEEDED	--	3, 5	details
#10	RUNTIME ERROR	0.98 s	3, 5	details
#11	RUNTIME ERROR	0.89 s	3, 5	details
#12	TIME LIMIT EXCEEDED	--	3, 5	details
#13	RUNTIME ERROR	0.92 s	4, 5	details
#14	TIME LIMIT EXCEEDED	--	5	details
#15	TIME LIMIT EXCEEDED	--	3, 5	details
#16	TIME LIMIT EXCEEDED	--	5	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:131:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<v.size(); ++i){
                       ~^~~~~~~~~
input/code.cpp:144:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (i!=(v.size()-1)){
                     ~^~~~~~~~~~~~~~
input/code.cpp:202: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:203: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], v;
set<int> s;

void poista(int a, int b){
    set<int> s1, s2;
    for (auto u:ans[a]){
        s1.insert(u);
    }
    while (ans[a].size()) ans[a].pop_back();
    for (auto u:s1) if (u!=b) ans[a].PB(u);
    for (auto u:ans[b]){
        s1.insert(u);
    }
    while (ans[b].size()) ans[b].pop_back();
    for (auto u:s1) if (u!=a) ans[b].PB(u);
}

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;
    lisaa2(a, edel);
    for (auto u:r[a]){
        if (u!=edel){
            f(u, a, k+1);
        }
    }
    if (yes==0){
        poista(a, edel);
    }
    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=0; 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;
        }
        s.clear();
        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;
        }
        while (v.size()) v.pop_back();
        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;
        vector<int> vas;
        while (true){
            int b=0;
            if (ans[a][0]!=edel) b=ans[a][0];
            else b=ans[a][1];
            if (b==(a+1)) vas.PB(2);
            if (b==(a-1)) vas.PB(4);
            if (b==(a+m)) vas.PB(3);
            if (b==(a-m)) vas.PB(1);
            if (b==(y2-1)*m+x2) break;
            edel=a;
            a=b;
        }
        if (kaanto) {
            reverse(vas.begin(), vas.end());
            for (auto u:vas){
                if (u==1) cout << "D";
                if (u==2) cout << "L";
                if (u==3) cout << "U";
                if (u==4) cout << "R";
            }
        }
        else{
            for (auto u:vas) {
                if (u==1) cout << "U";
                if (u==2) cout << "R";
                if (u==3) cout << "D";
                if (u==4) cout << "L";
            }
        }
        cout << "\n";
    }
}

Test details

Test 1

Group: 1, 5

Verdict: ACCEPTED

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
`YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...` Truncated

Test 2

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

Test 3

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

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)

Test 4

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

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: TIME LIMIT EXCEEDED

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
(empty)

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

Test 9

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

Test 10

Group: 3, 5

Verdict: RUNTIME ERROR

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` view save

Test 11

Group: 3, 5

Verdict: RUNTIME ERROR

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` view save

Test 12

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

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)

Test 13

Group: 4, 5

Verdict: RUNTIME ERROR

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
(empty)

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: TIME LIMIT EXCEEDED

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
(empty)

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)