Submission #895557

#TimeUsernameProblemLanguageResultExecution timeMemory
895557marvinthangNavigation 2 (JOI21_navigation2)C++17
100 / 100
534 ms2584 KiB
/************************************* * author: marvinthang * * created: 30.12.2023 10:47:39 * *************************************/ #include "Anna.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define left ___left #define right ___right #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define MASK(i) (1LL << (i)) #define BIT(x, i) ((x) >> (i) & 1) #define __builtin_popcount __builtin_popcountll #define ALL(v) (v).begin(), (v).end() #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define REPD(i, n) for (int i = (n); i-- > 0; ) #define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; ) #define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u) #define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u) #ifdef LOCAL #include "debug.h" #else #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define DB(...) 23 #define db(...) 23 #define debug(...) 23 #endif template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; } template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; } template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; } template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); } template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; } // end of template void Anna(int N, int K, vector <int> R, vector <int> C) { auto get_idx = [&] (int x, int y, int i) { x -= R[i]; y -= C[i]; if (y < -1) return 2; if (y > +1) return 3; if (x < -1) return 4; if (x > +1) return 5; ++x; ++y; return x * 3 + y + 6; }; vector <vector <int>> board(N, vector<int>(N)); auto check = [&] (int pos) { int px = pos / 3, py = pos % 3; REP(x, N) REP(y, N) { int id = (x + px) % 3 * 3 + (y + py) % 3; if (id < K) { board[x][y] = get_idx(x, y, id); if (board[x][y] == 14) return false; } else if (id == K) board[x][y] = -1; else board[x][y] = 1; } return true; }; REP(pos, 9) if (check(pos)) { vector <bool> used(14); REP(i, N) REP(j, N) if (board[i][j] >= 0) used[board[i][j]] = true; int mi = find(1 + ALL(used), false) - used.begin(); REP(i, N) REP(j, N) { if (board[i][j] == -1) board[i][j] = mi - 1; else if (board[i][j] > mi) --board[i][j]; SetFlag(i, j, board[i][j]); } return; } }
/************************************* * author: marvinthang * * created: 30.12.2023 11:08:47 * *************************************/ #include "Bruno.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define left ___left #define right ___right #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define MASK(i) (1LL << (i)) #define BIT(x, i) ((x) >> (i) & 1) #define __builtin_popcount __builtin_popcountll #define ALL(v) (v).begin(), (v).end() #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define REPD(i, n) for (int i = (n); i-- > 0; ) #define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; ) #define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u) #define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u) #ifdef LOCAL #include "debug.h" #else #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define DB(...) 23 #define db(...) 23 #define debug(...) 23 #endif template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; } template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; } template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; } template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); } template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; } // end of template vector <int> Bruno(int K, vector <int> value) { int pos = find(ALL(value), 1) - value.begin(); int nxt = pos / 3 * 3 + (pos % 3 + 1) % 3; if (value[nxt] == 1) pos = nxt; int px = (pos / 3 + 1) % 3, py = (pos % 3 + 1) % 3; int mi = -1; REP(i, 9) { int x = (i / 3 - px + 3) % 3, y = (i % 3 - py + 3) % 3; int id = x * 3 + y; if (id == K) mi = value[i]; } REP(i, 9) if (value[i] > mi) ++value[i]; vector <int> res(K); REP(i, 9) { int x = (i / 3 - px + 3) % 3, y = (i % 3 - py + 3) % 3; int id = x * 3 + y; if (id < K) { if (value[i] < 6) res[id] = value[i] - 2; else { x = value[i] / 3 - i / 3 - 2; y = value[i] % 3 - i % 3; if (y) res[id] = y > 0; else if (x) res[id] = 2 + (x > 0); else res[id] = 4; } } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...