| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 389677 | rama_pang | Navigation 2 (JOI21_navigation2) | C++17 | 1 ms | 452 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
pair<int, int> GetSpecial(pair<int, int> a, pair<int, int> b) {
/* List of classes determined by 2 special colors
Case 1:
000 000 000
000 000 000
110 101 011
000 000 000
110 101 011
000 000 000
110 101 011
000 000 000
000 000 000
Case 2:
000 000 000
001 010 100
100 001 010
001 010 100
100 001 010
000 000 000
100 001 010
000 000 000
001 010 100
Case 3:
000 000 000
010 100 001
100 001 010
010 100 001
100 001 010
000 000 000
100 001 010
000 000 000
010 100 001
Case 4:
000 000 000
100 001 010
100 001 010
100 001 010
100 001 010
000 000 000
100 001 010
000 000 000
100 001 010
*/
const vector<int> dx = {0, 1, 1, 1};
const vector<int> dy = {1, 0, 1, 2};
for (int d = 0; d < 4; d++) {
if ((a.first + dx[d]) % 3 == b.first &&
(a.second + dy[d]) % 3 == b.second) {
return a;
}
}
return b;
}
} // namespace
void Anna(int N, int K, vector<int> R, vector<int> C) {
// Solution:
// We mark a node (x, y), where x mod 3 = 0 and y mod 3 = 0 with
// color L. Then, for Bruno, when we look at the 9 viewable cells,
// we know which one has x mod 3 = 0 and y mod 3 = 0.
//
// After that, we can identify each cell having 1 of 9 equivalence
// classes. The i-th class will hold information about the i-th goal.
// For the i-th goal, we only need to keep track of 13 possible information:
// 9, if the goal is close (9-adjacent to the cell of the class), and 4
// if the goal is far away. This yield 13 (for goal information) + 1 (to
// determine which cell has class x mod 3 = 0 and y mod 3 = 0).
//
// Since there are only 7 goals, there are only 7 possible values for the
// case when the goal is close. We color the other 2 values with L, and,
// while more difficult, we can still determine the 9 class of each cell.
// With this, we only need 7 (goal is near) + 4 (goal is fat) + 1 (special
// color L) = 12 colors.
vector<vector<int>> has_goal(3, vector<int>(3));
for (int i = 0; i < K; i++) {
has_goal[R[i] % 3][C[i] % 3] = 1;
}
vector<pair<int, int>> no_goals;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (!has_goal[i][j]) {
no_goals.emplace_back(i, j);
}
}
}
assert(no_goals.size() >= 2);
no_goals.resize(2);
vector<vector<int>> goal(3, vector<int>(3, -1));
auto zero = GetSpecial(no_goals[0], no_goals[1]);
for (int i = 0, cnt = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int x = (zero.first + i) % 3;
int y = (zero.second + j) % 3;
if (pair(x, y) != no_goals[0] && pair(x, y) != no_goals[1]) {
goal[i][j] = cnt++;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (goal[i % 3][j % 3] == -1) {
SetFlag(i, j, 12);
} else {
int g = goal[i % 3][j % 3];
int close = -1;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (R[g] == i + di && C[g] == j + dj) {
assert(close == -1);
assert(goal[di + 1][dj + 1] != -1);
close = goal[di + 1][dj + 1] + 1;
}
}
}
if (close != -1) {
assert(1 <= close && close <= 7);
SetFlag(i, j, close);
} else {
if (i + 1 < R[g]) {
SetFlag(i, j, 8);
} else if (i - 1 > R[g]) {
SetFlag(i, j, 9);
} else if (j + 1 < C[g]) {
SetFlag(i, j, 10);
} else if (j - 1 > C[g]) {
SetFlag(i, j, 11);
} else {
assert(false);
}
}
}
}
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
pair<int, int> GetSpecial(pair<int, int> a, pair<int, int> b) {
/* List of classes determined by 2 special colors
Case 1:
000 000 000
000 000 000
110 101 011
000 000 000
110 101 011
000 000 000
110 101 011
000 000 000
000 000 000
Case 2:
000 000 000
001 010 100
100 001 010
001 010 100
100 001 010
000 000 000
100 001 010
000 000 000
001 010 100
Case 3:
000 000 000
010 100 001
100 001 010
010 100 001
100 001 010
000 000 000
100 001 010
000 000 000
010 100 001
Case 4:
000 000 000
100 001 010
100 001 010
100 001 010
100 001 010
000 000 000
100 001 010
000 000 000
100 001 010
*/
const vector<int> dx = {0, 1, 1, 1};
const vector<int> dy = {1, 0, 1, 2};
for (int d = 0; d < 4; d++) {
if ((a.first + dx[d]) % 3 == b.first &&
(a.second + dy[d]) % 3 == b.second) {
return a;
}
}
return b;
}
} // namespace
vector<int> Bruno(int K, vector<int> value) {
vector<int> res(K, -1);
vector<pair<int, int>> no_goals;
vector<vector<int>> values(3, vector<int>(3));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
values[i][j] = value[i * 3 + j];
if (values[i][j] == 12) {
no_goals.emplace_back(i, j);
}
}
}
assert(no_goals.size() == 2);
vector<vector<int>> goal(3, vector<int>(3, -1));
auto zero = GetSpecial(no_goals[0], no_goals[1]);
for (int i = 0, cnt = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int x = (zero.first + i) % 3;
int y = (zero.second + j) % 3;
if (pair(x, y) != no_goals[0] && pair(x, y) != no_goals[1]) {
goal[i][j] = cnt++;
}
}
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int g = goal[(i + 3 - zero.first) % 3][(j + 3 - zero.second) % 3];
int close = values[i][j];
if (close == 12) {
continue;
}
// g-th goal has clue "close"
if (1 <= close && close <= 7) {
int Rg = -100, Cg = -100;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (goal[di + 1][dj + 1] + 1 == close) {
assert(Rg == -100 && Cg == -100);
Rg = i + di;
Cg = j + dj;
}
}
}
const auto Move = [&](int sr, int sc, int er, int ec) {
if (sr < er) {
return 2;
} else if (sr > er) {
return 3;
} else if (sc < ec) {
return 0;
} else if (sc > ec) {
return 1;
} else {
return 4;
}
};
res[g] = Move(1, 1, Rg, Cg);
} else {
if (close == 8) {
res[g] = 2;
} else if (close == 9) {
res[g] = 3;
} else if (close == 10) {
res[g] = 0;
} else if (close == 11) {
res[g] = 1;
}
}
}
}
return res;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||