CSES - Datatähti 2021 alku - Results
Submission details
Task:Ratsun reitit
Sender:jogr
Submission time:2020-09-28 18:29:19 +0300
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED27
#2ACCEPTED31
#3ACCEPTED42
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s2, 3details
#9ACCEPTED0.01 s2, 3details
#10ACCEPTED0.01 s2, 3details
#11ACCEPTED0.01 s3details
#12ACCEPTED0.01 s3details
#13ACCEPTED0.01 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:100:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int ti = 0; ti < last_layer.size(); ti++) {
                          ~~~^~~~~~~~~~~~~~~~~~~

Code

/*
possible moves
( 2 , 1)
( 2 , -1)
(-2 , 1)
(-2 , -1)
( 1 , 2)
( 1 , -2)
(-1 , 2)
(-1 , -2)
possible moves are:
one either of the 1 or 2 and both can be negative or positive
*/
class vec2 {
public:
int x;
int y;
vec2(int x, int y) {
this->x = x;
this->y = y;
}
};
#include <iostream>
#include <vector>
using namespace std;
int size; // size of the board size x size
int** num_moves; // xy
int tiles_left;
#define NUM_POSSIBLE_MOVES 8
vec2 possible_moves[] = {
vec2( 2 , 1),
vec2( 2 , -1),
vec2(-2 , 1),
vec2(-2 , -1),
vec2( 1 , 2),
vec2( 1 , -2),
vec2(-1 , 2),
vec2(-1 , -2)
};
// is tile within board
bool is_move_valid(vec2 coord) {
int max_coord = size - 1;
return (coord.x <= max_coord && coord.x >= 0) && (coord.y <= max_coord && coord.y >= 0);
}
// check if the tile is already set
bool is_move_set(vec2 coord) {
return num_moves[coord.x][coord.y] != -1;
}
// sets a move to the output
void set_move(vec2 coord, int num) {
tiles_left--;
num_moves[coord.x][coord.y] = num;
}
int main() {
cin >> size;
// init number of moves
num_moves = new int*[size];
for (int i = 0; i < size; i++) {
num_moves[i] = new int[size];
}
// set the values to -1 for keeping track of all unset tiles
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
num_moves[x][y] = -1;
}
}
tiles_left = size * size;
vec2 start = vec2(0, 0);
// the last layer is the latest tiles, that the cavalry can be moved in the least number of moves
vector<vec2> last_layer;
last_layer.push_back(start);
int moves_made = 0;
// set the first move (0, 0)
set_move(start, moves_made++);
// run the loop until every tile has a number of moves
while (tiles_left > 0) {
vector<vec2> new_layer;
for (int ti = 0; ti < last_layer.size(); ti++) {
for (int mi = 0; mi < NUM_POSSIBLE_MOVES; mi++) {
// get the tile
vec2 tile = vec2(last_layer[ti].x + possible_moves[mi].x, last_layer[ti].y + possible_moves[mi].y);
// if not valid, or is already set, skip
if (!is_move_valid(tile) || is_move_set(tile)) continue;
// if is valid
// push to the new layer
new_layer.push_back(tile);
// set move to the output
set_move(tile, moves_made);
}
}
last_layer = new_layer;
moves_made++;
}
// print the output
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
cout << num_moves[y][x] << " ";
}
cout << endl;
}
return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
4

correct output
0 3 2 5 
3 4 1 2 
2 1 4 3 
5 2 3 2 

user output
0 3 2 5 
3 4 1 2 
2 1 4 3 
5 2 3 2 

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
5

correct output
0 3 2 3 2 
3 4 1 2 3 
2 1 4 3 2 
3 2 3 2 3 
2 3 2 3 4 

user output
0 3 2 3 2 
3 4 1 2 3 
2 1 4 3 2 
3 2 3 2 3 
2 3 2 3 4 

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
6

correct output
0 3 2 3 2 3 
3 4 1 2 3 4 
2 1 4 3 2 3 
3 2 3 2 3 4 
2 3 2 3 4 3 
...

user output
0 3 2 3 2 3 
3 4 1 2 3 4 
2 1 4 3 2 3 
3 2 3 2 3 4 
2 3 2 3 4 3 
...

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
7

correct output
0 3 2 3 2 3 4 
3 4 1 2 3 4 3 
2 1 4 3 2 3 4 
3 2 3 2 3 4 3 
2 3 2 3 4 3 4 
...

user output
0 3 2 3 2 3 4 
3 4 1 2 3 4 3 
2 1 4 3 2 3 4 
3 2 3 2 3 4 3 
2 3 2 3 4 3 4 
...
Truncated

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
8

correct output
0 3 2 3 2 3 4 5 
3 4 1 2 3 4 3 4 
2 1 4 3 2 3 4 5 
3 2 3 2 3 4 3 4 
2 3 2 3 4 3 4 5 
...

user output
0 3 2 3 2 3 4 5 
3 4 1 2 3 4 3 4 
2 1 4 3 2 3 4 5 
3 2 3 2 3 4 3 4 
2 3 2 3 4 3 4 5 
...
Truncated

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
9

correct output
0 3 2 3 2 3 4 5 4 
3 4 1 2 3 4 3 4 5 
2 1 4 3 2 3 4 5 4 
3 2 3 2 3 4 3 4 5 
2 3 2 3 4 3 4 5 4 
...

user output
0 3 2 3 2 3 4 5 4 
3 4 1 2 3 4 3 4 5 
2 1 4 3 2 3 4 5 4 
3 2 3 2 3 4 3 4 5 
2 3 2 3 4 3 4 
...
Truncated

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
10

correct output
0 3 2 3 2 3 4 5 4 5 
3 4 1 2 3 4 3 4 5 6 
2 1 4 3 2 3 4 5 4 5 
3 2 3 2 3 4 3 4 5 6 
2 3 2 3 4 3 4 5 4 5 
...

user output
0 3 2 3 2 3 4 5 4 5 
3 4 1 2 3 4 3 4 5 6 
2 1 4 3 2 3 4 5 4 5 
3 2 3 2 3 4 3 4 5 6 
2 3 2 
...
Truncated

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
25

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
49

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
50

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 11

Group: 3

Verdict: ACCEPTED

input
75

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 12

Group: 3

Verdict: ACCEPTED

input
99

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 13

Group: 3

Verdict: ACCEPTED

input
100

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated