CSES - Datatähti 2021 alku - Results
Submission details
Task:Arpakuutiot
Sender:jogr
Submission time:2020-10-11 01:40:01 +0300
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#20.01 s1, 2details
#30.01 s1, 2details
#40.01 s1, 2details
#50.01 s1, 2details
#60.01 s1, 2details
#70.01 s1, 2details
#80.01 s1, 2details
#9ACCEPTED0.01 s1, 2details
#100.01 s1, 2details
#110.01 s2details
#120.01 s2details
#130.01 s2details
#140.01 s2details
#150.01 s2details
#160.01 s2details
#170.01 s2details
#180.01 s2details
#190.01 s2details
#200.01 s2details
#210.01 s2details
#220.01 s2details
#230.01 s2details
#240.01 s2details
#250.01 s2details
#260.01 s2details
#270.01 s2details
#280.01 s2details
#290.01 s2details
#300.01 s2details
#31ACCEPTED0.01 s1, 2details

Compiler report

input/code.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > simplify(std::vector<std::__cxx11::basic_string<char> >)':
input/code.cpp:202:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int s = 0; s < straights.size(); s++) {
                     ~~^~~~~~~~~~~~~~~~~~
input/code.cpp:198:10: warning: unused variable 'is_vertical' [-Wunused-variable]
     bool is_vertical = true;
          ^~~~~~~~~~~
input/code.cpp:200:9: warning: unused variable 'limit' [-Wunused-variable]
     int limit = stindex;
         ^~~~~
input/code.cpp: In function 'endpoint find_base(std::vector<std::__cxx11::basic_string<char> >)':
input/code.cpp:256:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
input/code.cpp: In function 'int get_opposite(std::vector<std::__cxx11::basic_string<char> >, endpoint)':
input/code.cpp:270:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/*
Main problem - how is the cube represented

1. Create cubes from all the numbers in the input - with only sides next to the base.
2. Merge the cubes into one cube.
*/

vector<vector<string>> inp;

class endpoint {
public:
    int x;
    int y;
    
    bool operator==(endpoint b) {
        return (this->x == b.x && this->y == b.y);
    }
};

class straight {
public:
    endpoint ep[2];
    bool is_vertical;
    
    bool operator==(straight b) {
        return (this->ep[0] == b.ep[0] && this->ep[1] == b.ep[1]);
    }
};

class cube {
public:
    int base;
    int front;
    int right;
    int back;
    int left;
    int opposite;
    
    cube() {
        this->base = -1;
        this->front = -1;
        this->right = -1;
        this->back = -1;
        this->left = -1;
        this->opposite = -1;
    }
    
    cube rotate_with_base_and_front(int new_base, int new_front) {
        cube c = *this;
        cube temp = *this;
        
        if (new_front == temp.front) return c;
        else if (new_front == temp.left) {
            c.front = temp.left;
            c.left = temp.back;
            c.back = temp.right;
            c.right = temp.front;
        }
        else if (new_front == temp.back) {
            c.front = temp.back;
            c.left = temp.right;
            c.back = temp.front;
            c.right = temp.left;
        }
        else if (new_front == temp.right) {
            c.front = temp.right;
            c.left = temp.front;
            c.back = temp.left;
            c.right = temp.back;
        }
        else if (new_front == temp.opposite) { // upper face
            c.front = temp.opposite;
            c.opposite = temp.back;
            c.back = temp.base;
            c.base = temp.front;
        }
        else if (new_front == temp.base) { // bottom face
            c.front = temp.base;
            c.base = temp.back;
            c.back = temp.opposite;
            c.opposite = temp.front;
        }
        
        temp = c;
        if (new_base == temp.base) return c;
        //else if (new_base == temp.front) {
        //    c.base = temp.front;
        //    c.front = temp.opposite;
        //    c.opposite = temp.back;
        //    c.back = temp.base;
        //}
        //else if (new_base == temp.opposite) {
        //    c.base = temp.opposite;
        //    c.front = temp.back;
        //    c.opposite = temp.base;
        //    c.back = temp.front;
        //}
        //else if (new_base == temp.back) {
        //    c.base = temp.back;
        //    c.back = temp.opposite;
        //    c.opposite = temp.front;
        //    c.front = temp.base;
        //}
        else if (new_base == temp.opposite) {
            c.base = temp.opposite;
            c.right = temp.left;
            c.opposite = temp.base;
            c.left = temp.right;
        }
        else if (new_base == temp.right) {
            c.base = temp.right;
            c.right = temp.opposite;
            c.opposite = temp.left;
            c.left = temp.base;
        }
        else if (new_base == temp.left) {
            c.base = temp.left;
            c.left = temp.opposite;
            c.opposite = temp.right;
            c.right = temp.base;
        }
        
        return c;
    }
    
    bool operator==(cube b) {
        cube nb = b.rotate_with_base_and_front(this->base, this->front);
        //cout << this->base << " : " << nb.base << endl;
        if (this->base != nb.base) return false;
        if (this->front != nb.front) return false;
        if (this->right != nb.right) return false;
        if (this->back != nb.back) return false;
        if (this->left != nb.left) return false;
        if (this->opposite != nb.opposite) return false;
        return true;
    }
};

vector<string> simplify(vector<string> data) { // creates a straight of four, if doesn't already exist
    vector<straight> straights;
    int stindex = 0;
    
    int offsetx[] = {1, -1, 0, 0};
    int offsety[] = {0, 0, 1, -1};
    for (int y=0; y<5; y++) {
        bool complete = false;
        for (int x=0; x<5; x++) {
            char c = data[y].at(x);
            if (c == '.') continue;
            straight s;
            bool isfour = false;
            for (int i=0; i<4; i++) {
                int ypos = y + (offsety[i]);
                int xpos = x + (offsetx[i]);
                if (xpos < 0 || xpos > 4 || ypos < 0 || ypos > 4) continue;
                char ec = data[ypos].at(xpos);
                if (ec == '.') continue;
                ypos = y + (offsety[i] * 2);
                xpos = x + (offsetx[i] * 2);
                if (xpos < 0 || xpos > 4 || ypos < 0 || ypos > 4) continue;
                ec = data[ypos].at(xpos);
                if (ec == '.') continue;
                //  creates endpoints in case its a straight of three
                s.ep[0].x = x;
                s.ep[0].y = y;
                s.ep[1].x = x + (offsetx[i] * 2);
                s.ep[1].y = y + (offsety[i] * 2);
                complete = true;
                ypos = y + (offsety[i] * 3);
                xpos = x + (offsetx[i] * 3);
                if (xpos < 0 || xpos > 4 || ypos < 0 || ypos > 4) continue;
                ec = data[ypos].at(xpos);
                if (ec == '.') continue;
                s.ep[0].x = x;
                s.ep[0].y = y;
                s.ep[1].x = x + (offsetx[i] * 3);
                s.ep[1].y = y + (offsety[i] * 3);
                isfour = true;
            }
            if (isfour) return data;
            if (complete) {
                straights.push_back(s);
                stindex++;
                //for (straight sa: straights) {
                    //cout << sa.ep[0].x << " : " << sa.ep[0].y << " :: " << sa.ep[1].x << " : " << sa.ep[1].y << endl;
                //}
                //cout << endl << endl;
            }
        }
    }
    bool is_vertical = true;
    
    int limit = stindex;
    
    for (int s = 0; s < straights.size(); s++) {
        int diffx = straights[s].ep[0].x - straights[s].ep[1].x; 
        diffx = (diffx == 0) ? 0 : (int)((float)diffx / (float)abs(diffx));
        //cout << diffx << endl;
        int diffy = straights[s].ep[0].y - straights[s].ep[1].y; 
        diffy = (diffy == 0) ? 0 : (int)((float)diffy / (float)abs(diffy));
        int xx ,xy;
        xx = straights[s].ep[0].x + diffx;
        xy = straights[s].ep[0].y + diffy;
        if (xy < 0 || xy > 4 || xx < 0 || xx > 4) continue;
        //data[xy].replace(xx, 1, "b");
        for (int i=0; i<2; i++) {
                int ypos = xy + (diffx * offsetx[i]); // swap the difference, so the numbers are looked from the opposite direction of the straight
                int xpos = xx + (diffy * offsetx[i]);
                if (xpos >= 0 || xpos <= 4 || xpos >= 0 || xpos <= 4)  {
                    char ec = data[ypos][xpos];
                    //data[ypos].replace(xpos, 1, "c");
                    if (ec != '.') {
                        data[xy].replace(xx, 1, &ec);
                        data[ypos].replace(xpos, 1, ".");
                        //cout << endl;
                        return data;
                    }
                }
        }
    } 
    return data;   
}

endpoint find_base(vector<string> data) {
    int offsetx[] = {1, -1, 0, 0};
    int offsety[] = {0, 0, 1, -1};
    
    for (int y=0; y<5; y++) {
        for (int x=0; x<5; x++) {
            char c = data[y].at(x);
            int numbers_around = 0;
            if (c == '.') continue;
            for (int i=0; i<4; i++) {
                int ypos = y + (offsety[i]);
                int xpos = x + (offsetx[i]);
                if (xpos < 0 || xpos > 4 || ypos < 0 || ypos > 4) continue;
                char ec = data[ypos].at(xpos);
                if (ec == '.') continue;
                numbers_around++;
            }
            if (numbers_around >= 3) {
                endpoint ep;
                ep.x = x;
                ep.y = y;
                return ep;
            }
        }
    }
}

int get_opposite(vector<string> data, endpoint base) {
    int offsetx[] = {2, -2, 0, 0};
    int offsety[] = {0, 0, 2, -2};
    
    for (int i=0; i<4; i++) {
        int ypos = base.y + (offsety[i]);
        int xpos = base.x + (offsetx[i]);
        if (xpos < 0 || xpos > 4 || ypos < 0 || ypos > 4) continue;
        char ec = data[ypos].at(xpos);
        if (ec == '.') continue;
        return atoi(&ec);
    }
}


int getvalue(vector<string> data, int x, int y) { // for create_cube()
    if (x < 0 || x > 4 || y < 0 || y > 4) return -1;
    else {
        char c = data[y][x];
        if (c == '.') return -1;
        return atoi(&c);
    }
}
cube create_cube(vector<string> data) {
    endpoint base = find_base(data);
    cube c;
    c.base = -1;
    c.front = -1;
    c.right = -1;
    c.back = -1;
    c.left = -1;
    
    c.base = getvalue(data, base.x, base.y);
    c.front = getvalue(data, base.x, base.y - 1);;
    c.right = getvalue(data, base.x + 1, base.y);
    c.back = getvalue(data, base.x, base.y + 1);
    c.left = getvalue(data, base.x - 1, base.y);
    c.opposite = get_opposite(data, base);
    
    int check[6] = { c.base, c.front, c.right, c.back, c.left, c.opposite };
    /*for (int i = 0; i < 6; i++) {
        if (check[i] == -1) {
            for (int x = 1; x <= 6; x++){
                bool isset  = false;
                for (int ii = 0; ii < 6; ii++) {
                    if (check[ii] == x) isset = true;
                    
                }
                if (!isset) {
                    switch (i) {
                        case 0:
                            c.base = x;
                            break;
                        case 1:
                            c.front = x;
                            break;
                        case 2:
                            c.right = x;
                            break;
                        case 3:
                            c.back = x;
                            break;
                        case 4:
                            c.left = x;
                            break;                        
                        case 5:
                            c.opposite = x;
                            break;
                    }
                }
                check[i] = x;
            }
        }
    }*/
    for (int i = 0; i < 6; i++) {
        if (check[i] == -1) {
            int x = 21 - (c.base + c.front + c.right + c.back + c.left + c.opposite) - 1;
            if (i == 0) c.base = x;
            else if (i == 1) c.front = x;
            else if (i == 2) c.right = x;
            else if (i == 3) c.back = x;
            else if (i == 4) c.left = x;
            else if (i == 5) c.opposite = x;
            check[i] = x;
        }
    }
    //for (int i = 0; i < 6; i++) {
    //    cout << check[i] << ", ";
    //}
    //cout << endl;
    return c;
}

int main()
{
    int count;
    cin >> count;
    
    for (int i = 0; i < count; i++) {
        string temp; 
        vector<string> vec;
        cin >> temp; vec.push_back(temp); temp.clear();
        cin >> temp; vec.push_back(temp); temp.clear();
        cin >> temp; vec.push_back(temp); temp.clear();
        cin >> temp; vec.push_back(temp); temp.clear();
        cin >> temp; vec.push_back(temp); temp.clear();
        inp.push_back(vec);
    }
    
    
    for (int i = 0; i < count; i++) {
        inp[i] = simplify(inp[i]);
    }
    
    vector<cube> cubes;
    for (int i = 0; i < count; i++){
        cubes.push_back(create_cube(inp[i]));
    }
    
    //cout << cubes[0].rotate_with_base_and_front(5, 2).base       << endl;
    //cout << cubes[0].rotate_with_base_and_front(5, 2).front      << endl;
    //cout << cubes[0].rotate_with_base_and_front(5, 2).right      << endl;
    //cout << cubes[0].rotate_with_base_and_front(5, 2).back       << endl;
    //cout << cubes[0].rotate_with_base_and_front(5, 2).left       << endl;
    //cout << cubes[0].rotate_with_base_and_front(5, 2).opposite   << endl;
    
    for (int i = 0; i < count; i++) {
        int counter = 0;
        for (int j = 0; j < count; j++) {
            if (i == j) continue;
            if (cubes[i] == cubes[j]) {
                if (j < (count - 2)) cout << (j + 1) << " ";
                else cout << (j + 1);
                counter++;
            }
        }
        if (counter == 0) cout << "-" << endl;
        else if ( i < (count - 1)) cout << endl;
    }
    
    /*for (vector<string> v: inp){
        for (string s: v) {
            cout << s << endl;
        }
        endpoint ep = find_base(v);
        cout << v[ep.y][ep.x] << " : " << get_opposite(v, ep);
        cout << endl;
    }*/
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
3
165..
.4...
.3...
.2...
...

correct output
3
-
1

user output
3
-

Test 2

Group: 1, 2

Verdict:

input
5
264..
.5...
.3...
.1...
...

correct output
3
4 5
1
2 5
2 4

user output

45

2 5
2 4

Test 3

Group: 1, 2

Verdict:

input
5
152..
.4...
.3...
.6...
...

correct output
3 5
4
1 5
2
1 3

user output

4
1 5


Test 4

Group: 1, 2

Verdict:

input
5
142..
.6...
.3...
.5...
...

correct output
4 5
3
2
1 5
1 4

user output
5


5
1 4

Test 5

Group: 1, 2

Verdict:

input
5
123..
.4...
.6...
.5...
...

correct output
3
4 5
1
2 5
2 4

user output

45

2 5
2 4

Test 6

Group: 1, 2

Verdict:

input
5
213..
.6...
.4...
.5...
...

correct output
4 5
3
2
1 5
1 4

user output
45


1 5
1 4

Test 7

Group: 1, 2

Verdict:

input
5
314..
.5...
.2...
.6...
...

correct output
3
4 5
1
2 5
2 4

user output

45

2 5
2 4

Test 8

Group: 1, 2

Verdict:

input
5
163..
.2...
.5...
.4...
...

correct output
4 5
3
2
1 5
1 4

user output
45


1 5
1 4

Test 9

Group: 1, 2

Verdict: ACCEPTED

input
5
264..
.1...
.3...
.5...
...

correct output
2 3
1 3
1 2
5
4

user output
2 3 
1 3 
1 2 
5
4

Test 10

Group: 1, 2

Verdict:

input
5
214..
.3...
.5...
.6...
...

correct output
5
3 4
2 4
2 3
1

user output
5
3 4



Test 11

Group: 2

Verdict:

input
10
.41..
.5...
.2...
36...
...

correct output
9
4 6 8
7 10
2 6 8
-
...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::replace: __pos (which is 18446744073709551615) > this->size() (which is 4)

Test 12

Group: 2

Verdict:

input
10
5....
1436.
.2...
.....
...

correct output
5 8
6 10
4 7 9
3 7 9
1 8
...

user output
5 8 
-
4 7 9
3 7 
1 8 
...

Test 13

Group: 2

Verdict:

input
10
2....
41...
.63..
.5...
...

correct output
4 9 10
5 6 7 8
-
1 9 10
2 6 7 8
...

user output
4 10
5 6 7 
-

2 7 
...

Test 14

Group: 2

Verdict:

input
10
1....
634..
..52.
.....
...

correct output
2 3 4 5 6 9 10
1 3 4 5 6 9 10
1 2 4 5 6 9 10
1 2 3 5 6 9 10
1 2 3 4 6 9 10
...

user output
-

9
-
-
...

Test 15

Group: 2

Verdict:

input
10
.2...
4516.
3....
.....
...

correct output
5 7 9 10
8
4 6
3 6
1 7 9 10
...

user output
(empty)

Test 16

Group: 2

Verdict:

input
10
.56..
.2...
.4...
31...
...

correct output
4 9
3 5 10
2 5 10
1 9
2 3 10
...

user output
7 10
-
-
9
-
...

Test 17

Group: 2

Verdict:

input
10
..62.
.31..
45...
.....
...

correct output
2 3 4 8
1 3 4 8
1 2 4 8
1 2 3 8
6 7 9 10
...

user output
2 6 
1 6 

-
-
...

Test 18

Group: 2

Verdict:

input
10
532..
.4...
.1...
.6...
...

correct output
3 8 9
5 6
1 8 9
7 10
2 6
...

user output
3 8 9
5 6 
1 8 9
-
2 6 
...

Test 19

Group: 2

Verdict:

input
10
.64..
.1...
.3...
52...
...

correct output
2 5 6 7 8 9
1 5 6 7 8 9
4 10
3 10
1 2 6 7 8 9
...

user output
3 6 
-
1 6 
-
7 9
...

Test 20

Group: 2

Verdict:

input
10
.4...
326..
.1...
.5...
...

correct output
4 7 8
6 9 10
5
1 7 8
3
...

user output

6 9
-

-
...

Test 21

Group: 2

Verdict:

input
20
.6...
.4...
31...
.25..
...

correct output
3 7 11 16
6
1 7 11 16
5 19
4 19
...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::replace: __pos (which is 18446744073709551615) > this->size() (which is 4)

Test 22

Group: 2

Verdict:

input
20
3....
5614.
..2..
.....
...

correct output
7 10 11 17 20
12
4 9 13 15 18
3 9 13 15 18
8 14 16
...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::replace: __pos (which is 18446744073709551615) > this->size() (which is 4)

Test 23

Group: 2

Verdict:

input
20
42...
.316.
.5...
.....
...

correct output
5 12 13 15 18
16 20
6 8 14
9 19
1 12 13 15 18
...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::replace: __pos (which is 18446744073709551615) > this->size() (which is 4)

Test 24

Group: 2

Verdict:

input
20
..5..
.623.
41...
.....
...

correct output
2 6 11 12 13
1 6 11 12 13
5 16 18
7 14
3 16 18
...

user output
-
11 12 13 
-

16 
...

Test 25

Group: 2

Verdict:

input
20
.46..
53...
.1...
.2...
...

correct output
2 3 5 7 15 17 19
1 3 5 7 15 17 19
1 2 5 7 15 17 19
8 10 11 14
1 2 3 7 15 17 19
...

user output
2 3 5 7 19
1 3 5 19
1 2 5 7 19
10 
1 2 3 7 19
...

Test 26

Group: 2

Verdict:

input
20
.61..
.4...
35...
.2...
...

correct output
8 10 20
3 17 18 19
2 17 18 19
14 15
6 7 9 13
...

user output
8 20
18 19
18 
-
7 9 13 
...

Test 27

Group: 2

Verdict:

input
20
..2..
1463.
.5...
.....
...

correct output
2 3 5 6 9 20
1 3 5 6 9 20
1 2 5 6 9 20
11 19
1 2 3 6 9 20
...

user output
2 5 6 9 20
1 5 6 9 20
-
19
1 2 6 9 20
...

Test 28

Group: 2

Verdict:

input
20
...4.
5132.
6....
.....
...

correct output
2 8 10 12 13 19
1 8 10 12 13 19
4 5 15 16 17
3 5 15 16 17
3 4 15 16 17
...

user output
-
8 10 12 19
4 15 16 
3 15 16 
-
...

Test 29

Group: 2

Verdict:

input
20
.2...
.31..
45...
6....
...

correct output
5 8 9 14 17
3 10 16
2 10 16
13 15 19
1 8 9 14 17
...

user output
5 8 9 17 
10 16 
-
13 19
1 8 9 17 
...

Test 30

Group: 2

Verdict:

input
20
3....
452..
.1...
.6...
...

correct output
3 7 8 9 14 15 16 19
4 12 13 17
1 7 8 9 14 15 16 19
2 12 13 17
11 20
...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::replace: __pos (which is 18446744073709551615) > this->size() (which is 4)

Test 31

Group: 1, 2

Verdict: ACCEPTED

input
2
546..
.3...
.2...
.1...
...

correct output
-
-

user output
-
-