# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
386319 | model_code | Navigation 2 (JOI21_navigation2) | C++17 | 974 ms | 1124 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 <vector>
#include <algorithm>
#include "Anna.h"
namespace {
int encode(int dr, int dc) {
if(dc >= +2) return 2;
if(dc <= -2) return 3;
if(dr >= +2) return 4;
if(dr <= -2) return 5;
return (dr + 1) * 3 + (dc + 1) + 6;
}
}
void Anna(int N, int K, std::vector<int> R, std::vector<int> C) {
// Step #1 : Decide placement of "flags with number 1"
int optflag = 14; int optdelta = -1;
for(int delta = 0; delta < 9; ++delta) {
int maxflag = 1;
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
int precinct = ((i - delta / 3 + 3) % 3) * 3 + ((j - delta % 3 + 3) % 3);
if(precinct <= 6) {
maxflag = std::max(maxflag, encode(R[precinct] - i, C[precinct] - j));
}
}
}
if(optflag > maxflag) {
optflag = maxflag;
optdelta = delta;
}
}
// Step #2 : Make a provisional plan
std::vector<std::vector<int> > F(N, std::vector<int>(N, -1));
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
int precinct = ((i - optdelta / 3 + 3) % 3) * 3 + ((j - optdelta % 3 + 3) % 3);
if(precinct <= 6) {
F[i][j] = encode(R[precinct] - i, C[precinct] - j);
}
if(precinct == 8) {
F[i][j] = 1;
}
}
}
// Step #3. Apply "decrease-by-1" operation and finalize the plan
std::vector<bool> used(14, false);
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
if(F[i][j] != -1) {
used[F[i][j]] = true;
}
}
}
int non = std::find(used.begin() + 1, used.end(), false) - used.begin();
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
if(F[i][j] == -1) {
F[i][j] = non - 1;
}
else if(F[i][j] > non) {
--F[i][j];
}
SetFlag(i, j, F[i][j]);
}
}
}
#include <vector>
#include <utility>
#include <algorithm>
#include "Bruno.h"
std::vector<int> Bruno(int K, std::vector<int> value) {
// Step #1. Restore the plan before "decrease-by-1" operation
int center = std::find(value.begin(), value.end(), 1) - value.begin();
int rp = (center / 3 + 1) % 3, cp = (center % 3 + 1) % 3;
std::vector<int> precinct(9);
for(int i = 0; i < 9; ++i) {
precinct[i] = ((i / 3 - rp + 3) % 3) * 3 + ((i % 3 - cp + 3) % 3);
}
int seventh = std::find(precinct.begin(), precinct.end(), 7) - precinct.begin();
int non = value[seventh] + 1;
for(int i = 0; i < 9; ++i) {
if(value[i] >= non) {
++value[i];
}
}
// Step #2. Determine the next actions
std::vector<int> res(K, -1);
for(int i = 0; i < K; ++i) {
int ptr = std::find(precinct.begin(), precinct.end(), i) - precinct.begin();
int id = value[ptr] - 2;
if(id <= 3) {
res[i] = id;
}
else {
int isor = ((id - 4) / 3 - 1) + (ptr / 3 - 1);
int isoc = ((id - 4) % 3 - 1) + (ptr % 3 - 1);
if(isoc > 0) res[i] = 0;
else if(isoc < 0) res[i] = 1;
else if(isor > 0) res[i] = 2;
else if(isor < 0) res[i] = 3;
else res[i] = 4;
}
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |