QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#155188 | #7119. Longest Trip | yzy1 | 5 | 7ms | 4112kb | C++17 | 2.1kb | 2023-09-01 13:31:15 | 2024-04-28 06:55:07 |
Judging History
answer
#include <bits/stdc++.h>
#include "longesttrip.h"
#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>
#include "grader.cpp"
#else
#define dbg(x...) (0)
#endif
using namespace std;
using ll = long long;
// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))
template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
if (y < x) x = y;
}
namespace qingwa {
const int N = 1009;
mt19937 rnd;
int n, m;
bool flinit;
inline bool Ask(vector<int> x, vector<int> y) {
for (auto &v : x) --v;
for (auto &v : y) --v;
return are_connected(x, y);
}
namespace st2 {
bool vis[N];
int rnk[N];
vector<int> ans;
inline void Dfs1(int f) {
vis[f] = 1;
ans.push_back(f);
if ((int)ans.size() == n) return;
re (i, n) {
int t = rnk[i];
if (vis[t]) continue;
if (!Ask({f}, {t})) continue;
Dfs1(t);
if ((int)ans.size() == n) return;
}
vis[f] = 0;
}
inline vector<int> Work() {
re (i, n) vis[i] = 0;
ans.clear();
re (i, n) rnk[i] = i;
shuffle(rnk + 1, rnk + n + 1, rnd);
Dfs1(rnk[1]);
return ans;
}
} // namespace st2
inline vector<int> Work() {
if (m == 3) {
vector<int> vec;
re (i, n) vec.push_back(i);
return vec;
}
if (m == 2) return st2::Work();
return {};
}
} // namespace qingwa
std::vector<int> longest_trip(int N, int D) {
using namespace qingwa;
if (!flinit) flinit = 1, rnd.seed(random_device()());
n = N, m = D;
auto vec = Work();
for (auto &x : vec) --x;
return vec;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 3ms
memory: 3816kb
input:
341 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 ...
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 1 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 1 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 1 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 1 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 1 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 1 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 1 2...
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
103 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10 3 1 10...
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 10 0 1 2 3 4 5 6 7 8 9 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 10 0 1 2 3 4 5 6 7 8 9 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 10 0 1 2 3 4 5 6 7 8 9 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 10 0 1 2 3 4 5 6 7 8 9 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 10 0 1 2 3 4 5 6 7 8 9 3kC2Ia2048...
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
22 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 50 3 1 12 3 1 12 3 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3...
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
8 128 3 1 128 3 1 128 3 1 128 3 1 128 3 1 128 3 1 128 3 1 128 3 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 128 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 9...
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 4064kb
input:
4 256 3 1 256 3 1 256 3 1 256 3 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 256 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 9...
result:
ok
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 10
Accepted
time: 6ms
memory: 3808kb
input:
341 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 1 1 3 2 1 ...
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 0 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 2 1 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 2 1 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 0 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 0 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 1 0 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 2 0...
result:
ok
Test #7:
score: 0
Accepted
time: 4ms
memory: 4092kb
input:
103 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 10 2 1 1 1 1 1 1 1 1 ...
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 0 4 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 4 8 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 8 9 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 9 5 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 5 3 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 3 6 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 6 7...
result:
ok
Test #8:
score: 0
Accepted
time: 7ms
memory: 3824kb
input:
22 50 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 50 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 50 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 12 24 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 24 48 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 48 9 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 9 36 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 36 19 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 19 35 3kC2Ia2048BfyJVGojMUKKtilctlZKcB...
result:
ok
Test #9:
score: 0
Accepted
time: 7ms
memory: 3800kb
input:
8 128 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 128 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 95 1 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 116 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 116 52 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 52 4 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 4 109 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 109 123 3kC2Ia2048BfyJVGojMUKKtilctlZ...
result:
ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 3832kb
input:
4 256 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 39 143 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 143 192 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 192 66 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 66 14 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 14 85 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 85 230 3kC2Ia2048BfyJVGojMUKKtil...
result:
ok
Test #11:
score: -10
Wrong Answer
time: 1ms
memory: 4092kb
input:
341 3 2 1 0 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 0 1 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 1 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 0 1 1 0 2 3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 3 0 1 2
result:
wrong answer
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 4112kb
input:
341 3 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 0
result:
wrong answer
Subtask #4:
score: 0
Wrong Answer
Test #83:
score: 0
Wrong Answer
time: 1ms
memory: 3788kb
input:
341 3 1
output:
3kC2Ia2048BfyJVGojMUKKtilctlZKcB 1 0
result:
wrong answer