結果
問題 | No.1061 素敵な数列 |
ユーザー |
![]() |
提出日時 | 2022-08-15 10:48:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 9,554 bytes |
コンパイル時間 | 1,921 ms |
コンパイル使用メモリ | 186,728 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 23:28:20 |
合計ジャッジ時間 | 5,733 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <deque>#include <forward_list>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iostream>#include <limits>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <string>#include <tuple>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using lint = long long;using pint = pair<int, int>;using plint = pair<lint, lint>;struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;#define ALL(x) (x).begin(), (x).end()#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)template <typename T, typename V>void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }template <typename T> vector<T> sort_unique(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());return vec; }template <typename T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }template <typename T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }template <typename T, size_t sz> ostream &operator<<(ostream &os, const array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']';return os; }#if __cplusplus >= 201703Ltemplate <typename... T> istream &operator>>(istream &is, tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); returnis; }template <typename... T> ostream &operator<<(ostream &os, const tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }#endiftemplate <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os;}template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }template <typename T, typename TH> ostream &operator<<(ostream &os, const unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ',';os << '}'; return os; }template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os;}template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}';return os; }template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << '(' << pa.first << ',' << pa.second << ')';return os; }template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }template <typename TK, typename TV, typename TH> ostream &operator<<(ostream &os, const unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp)os << v.first << "=>" << v.second << ','; os << '}'; return os; }#ifdef HITONANODE_LOCALconst string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";#define dbg(x) cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET <<endl#define dbgif(cond, x) ((cond) ? cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ <<COLOR_RESET << endl : cerr)#else#define dbg(x) 0#define dbgif(cond, x) 0#endifvector<int> bruteforce(int N) {vector<int> state(N * 3, -1);vector<int> ret;int retcost = 1e9;int cost = 0;auto rec = [&](auto &&self, int nxt) -> void {// if (ret.size()) return;if (nxt == int(N)) {if (chmin(retcost, cost)) ret = state;return;}if (cost >= retcost) return;REP(i, state.size()) {if (state[i] != -1) continue;state[i] = nxt;FOR(j, i + 1, state.size()) {if (state[j] != -1) continue;state[j] = nxt;int k = -i + j * 2 + nxt;int addcost = 0;if (j < k and k < N * 3 and state[k] == -1) {// addcost = !(i < N and j >= N and j < N * 2 and k >= N * 2);addcost = (i + N != j);state[k] = nxt, cost += addcost;self(self, nxt + 1);state[k] = -1, cost -= addcost;}k = -i + j * 2 - nxt;if (j < k and k < N * 3 and state[k] == -1) {// addcost = !(i < N and j >= N and j < N * 2 and k >= N * 2);addcost = (i + N != j);state[k] = nxt, cost += addcost;self(self, nxt + 1);state[k] = -1, cost -= addcost;}state[j] = -1;}state[i] = -1;}};rec(rec, 0);return ret;}vector<int> solve(int n) {if (n == 1) return {0, 0, 0};if (n == 2) return {-1};if (n == 3) return {2, 0, 2, 1, 0, 1, 2, 0, 1};vector<deque<int>> deq(3);int nmd4 = n % 4;if (nmd4 == 0) {REP(d, 3) {deq[d].push_back(1);deq[d].push_back(0);}} else if (nmd4 == 1) {for (int x : {2, 1, 0}) deq[0].push_back(x);for (int x : {1, 2, 0}) deq[1].push_back(x);for (int x : {1, 2, 0}) deq[2].push_back(x);} else if (nmd4 == 2) {for (int x : {2, 3, 2, 2}) deq[0].push_back(x);for (int x : {0, 0, 0, 3}) deq[1].push_back(x);for (int x : {1, 1, 3, 1}) deq[2].push_back(x);} else if (nmd4 == 3) {for (int x : {3, 4, 0, 3, 3}) deq[0].push_back(x);for (int x : {4, 1, 0, 1, 1}) deq[1].push_back(x);for (int x : {2, 2, 0, 4, 2}) deq[2].push_back(x);} else {exit(1);}for (int y = nmd4 + 2; y + 3 < n; y += 4) {// y, y + 1, y + 2, y + 3int a = deq[0].front();deq[0].pop_front();deq[0].push_front(y);deq[0].push_front(a);deq[0].push_back(y + 1);deq[0].push_front(y + 2);deq[0].push_back(y + 3);deq[1].push_back(y);deq[1].push_front(y + 1);deq[1].push_front(y + 2);deq[1].push_back(y + 3);deq[2].push_back(y);deq[2].push_front(y + 1);deq[2].push_back(y + 2);deq[2].push_front(y + 3);}int a = deq[0].front();deq[0].pop_front();deq[0].push_front(n - 2);deq[0].push_front(a);deq[1].push_back(n - 2);deq[2].push_back(n - 2);deq[0].push_back(n - 1);deq[1].push_front(n - 1);deq[2].push_front(n - 1);vector<int> ret;for (auto &d : deq) {while (d.size()) {ret.push_back(d.front());d.pop_front();}}return ret;}bool check(int N, const vector<int> &V) {if (int(V.size()) != N * 3) return false;vector<vector<int>> poss(N);REP(i, V.size()) {int a = V[i];if (a < 0 or a >= N) return false;poss[a].push_back(i);}REP(n, N) {const auto &pos = poss.at(n);if (pos.size() != 3) return false;int diff = abs(pos[1] - pos[0] - (pos[2] - pos[1]));if (diff != n) {dbg(make_tuple(N, n, pos, diff));return false;}}return true;}int main() {// FOR(n, 3, 200) {// auto sol = solve(n);// if (!check(n, sol)) {// dbg(n);// dbg(sol);// exit(1);// }// }// FOR(n, 1, 21) {// dbg(bruteforce(n));// }int N;cin >> N;for (auto x : solve(N)) cout << x << ' ';cout << endl;}