QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311160 | #508. Nice sequence | jasper166 | 24 | 307ms | 17616kb | C++17 | 1.7kb | 2024-01-22 00:12:49 | 2024-01-22 00:12:50 |
Judging History
answer
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
const int N = 2e5 + 5;
int n, m;
vector <int> adj[N];
int deg[N], a[N];
bool check(int k) {
for (int i = 0; i <= k; ++i) {
if (i + m <= k) {
adj[i].push_back(i + m);
deg[i + m]++;
}
if (i >= n) {
adj[i].push_back(i - n);
deg[i - n]++;
}
}
queue <int> q;
for (int i = 0; i <= k; ++i)
if (deg[i] == 0)
q.push(i);
int cnt = 0;
vector <int> topo;
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
a[u] = ++cnt;
for (int v : adj[u]) {
deg[v]--;
if (deg[v] == 0) q.push(v);
}
}
for (int i = 0; i <= k; ++i) {
adj[i].clear();
deg[i] = 0;
}
// if the graph is cyclic then no topo order exists
return ((int) topo.size() == k + 1);
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
int l = 1, r = 2 * (m + n - 1);
int ans = -1;
// debug(check(3));
while (l <= r) {
int mi = (l + r) / 2;
if (check(mi)) {
ans = mi;
l = mi + 1;
}
else
r = mi - 1;
}
check(ans);
cout << ans << "\n";
for (int i = 1; i <= ans; ++i) {
cout << (a[i] - a[i - 1]) << " \n"[i == ans];
}
}
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 8228kb
input:
3 3 1 2 3 1 1
output:
2 1 1 3 2 -3 2 -1
result:
wrong answer Jury has the better answer : jans = 0, pans = -1
Subtask #2:
score: 9
Accepted
Test #14:
score: 9
Accepted
time: 0ms
memory: 8736kb
input:
10 2 2 3 2 4 2 5 2 2 6 2 7 2 8 9 2 10 2 2 11
output:
1 1 3 -2 3 -2 3 1 1 1 5 -3 4 -3 4 -3 5 1 -3 1 -3 1 7 4 -5 4 -5 4 -5 4 7 1 -3 1 -3 1 -3 1 9 -5 6 -5 6 -5 6 -5 6 -5 9 1 1 1 1 1 1 1 1 1 11 6 -7 6 -7 6 -7 6 -7 6 -7 6
result:
ok Ok
Test #15:
score: 0
Accepted
time: 2ms
memory: 8224kb
input:
10 12 2 2 13 14 2 2 15 2 16 17 2 18 2 19 2 20 2 21 2
output:
11 1 1 1 1 1 1 1 1 1 1 1 13 7 -8 7 -8 7 -8 7 -8 7 -8 7 -8 7 13 1 1 1 1 1 1 1 1 1 1 1 1 1 15 8 -9 8 -9 8 -9 8 -9 8 -9 8 -9 8 -9 8 15 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 17 -9 10 -9 10 -9 10 -9 10 -9 10 -9 10 -9 10 -9 10 -9 17 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 19 -10 11 -10 11 -10 11 -10 11 -10 11 -1...
result:
ok Ok
Test #16:
score: 0
Accepted
time: 2ms
memory: 9860kb
input:
10 2 22 2 23 2 24 2 25 26 2 2 27 28 2 2 29 30 2 31 2
output:
21 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 23 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 -13 12 23 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 25 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 -14 13 25 1 1 1 1 1...
result:
ok Ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 9076kb
input:
10 32 2 2 33 34 2 35 2 2 36 2 37 2 38 39 2 40 2 41 2
output:
31 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 33 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 -18 17 33 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 35 -18 19 -18 19 -18 19 -18 19 -18 19 -18 19 -18...
result:
ok Ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 8252kb
input:
10 2 42 43 2 2 44 45 2 46 2 2 47 48 2 2 49 50 2 2 51
output:
41 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 43 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 23 -22 43 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -...
result:
ok Ok
Test #19:
score: 0
Accepted
time: 5ms
memory: 9292kb
input:
10 2 1727 1728 2 1729 2 1730 2 1731 2 1732 2 2 1733 2 1734 2 1735 2 1736
output:
1727 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -865 864 -86...
result:
ok Ok
Test #20:
score: 0
Accepted
time: 15ms
memory: 9212kb
input:
10 2 8495 2 8496 2 8497 2 8498 8499 2 8500 2 2 8501 8502 2 8503 2 2 8504
output:
8495 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -4249 4248 -424...
result:
ok Ok
Test #21:
score: 0
Accepted
time: 4ms
memory: 9756kb
input:
10 2 3989 2 3990 2 3991 2 3992 2 3993 3994 2 3995 2 3996 2 2 3997 2 3998
output:
3989 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -1996 1995 -199...
result:
ok Ok
Test #22:
score: 0
Accepted
time: 17ms
memory: 8784kb
input:
10 9991 2 2 9992 2 9993 9994 2 9995 2 2 9996 2 9997 9998 2 9999 2 10000 2
output:
9991 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 4997 -4996 499...
result:
ok Ok
Test #23:
score: 0
Accepted
time: 6ms
memory: 8588kb
input:
10 2 5682 5683 2 5684 2 2 5685 2 5686 5687 2 2 5688 2 5689 2 5690 2 5691
output:
5681 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 1 -3 ...
result:
ok Ok
Subtask #3:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 2ms
memory: 9076kb
input:
10 7 1 1 5 1 1 10 1 1 4 3 1 1 6 1 2 1 9 8 1
output:
6 1 1 1 1 1 1 4 -1 -1 -1 -1 -1 9 1 1 1 1 1 1 1 1 1 3 -1 -1 -1 2 1 1 5 -1 -1 -1 -1 -1 1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 7 1 1 1 1 1 1 1
result:
wrong answer Jury has the better answer : jans = 0, pans = -1
Subtask #4:
score: 15
Accepted
Test #34:
score: 15
Accepted
time: 0ms
memory: 8636kb
input:
10 2 3 2 4 4 3 5 3 5 4 6 4 6 5 5 7 7 6 6 8
output:
3 2 -3 2 3 1 -3 1 5 -2 -2 5 -2 -2 6 3 -5 3 3 -5 3 7 -2 -2 -2 7 -2 -2 -2 7 1 -5 1 5 1 -5 1 9 -2 -2 -2 -2 9 -2 -2 -2 -2 10 -5 7 -5 7 -5 -5 7 -5 7 -5 11 -2 -2 -2 -2 -2 11 -2 -2 -2 -2 -2 11 1 3 1 3 1 -11 1 3 1 3 1
result:
ok Ok
Test #35:
score: 0
Accepted
time: 2ms
memory: 8872kb
input:
10 8 7 7 9 8 9 8 10 10 9 11 9 11 10 10 12 12 11 13 11
output:
13 -2 -2 -2 -2 -2 -2 13 -2 -2 -2 -2 -2 -2 14 -7 9 -7 9 -7 9 -7 -7 9 -7 9 -7 9 -7 15 2 2 2 2 2 2 2 -15 2 2 2 2 2 2 2 15 1 3 1 3 1 3 1 -15 1 3 1 3 1 3 1 17 -2 -2 -2 -2 -2 -2 -2 -2 17 -2 -2 -2 -2 -2 -2 -2 -2 18 9 -11 9 -11 9 -11 9 -11 9 9 -11 9 -11 9 -11 9 -11 9 19 -2 -2 -2 -2 -2 -2 -2 -2 -2 19 -2 -2 -...
result:
ok Ok
Test #36:
score: 0
Accepted
time: 1ms
memory: 8440kb
input:
10 13 12 14 12 14 13 15 13 15 14 14 16 15 16 17 15 17 16 16 18
output:
23 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 23 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 23 1 -5 1 -5 1 -5 1 -5 1 -5 1 21 1 -5 1 -5 1 -5 1 -5 1 -5 1 25 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 25 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 26 13 -15 13 -15 13 -15 13 -15 13 -15 13 -15 13 13 -15 13 -15 13 -15 13 -15 13 -15 13 -15 ...
result:
ok Ok
Test #37:
score: 0
Accepted
time: 0ms
memory: 8460kb
input:
10 18 17 17 19 18 19 18 20 20 19 21 19 21 20 20 22 21 22 21 23
output:
33 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 33 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 34 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 19 -17 35 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 -35 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok Ok
Test #38:
score: 0
Accepted
time: 0ms
memory: 9600kb
input:
10 23 22 22 24 23 24 25 23 24 25 26 24 26 25 25 27 27 26 26 28
output:
43 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 43 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 43 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 -43 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 45 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 -45 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok Ok
Test #39:
score: 0
Accepted
time: 170ms
memory: 16824kb
input:
10 83402 83404 52908 52906 74520 74521 24222 24221 1082 1083 8982 8980 10142 10141 34908 34906 58179 58181 50841 50843
output:
166803 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1...
result:
ok Ok
Test #40:
score: 0
Accepted
time: 180ms
memory: 17544kb
input:
10 20084 20083 10333 10331 98649 98648 72803 72804 40654 40655 1612 1614 26871 26873 5060 5062 60616 60615 6832 6830
output:
40165 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 ...
result:
ok Ok
Test #41:
score: 0
Accepted
time: 307ms
memory: 17616kb
input:
10 79524 79523 91096 91095 90747 90749 83462 83460 78387 78388 67918 67920 1682 1681 13180 13179 98702 98700 70766 70767
output:
159045 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2...
result:
ok Ok
Test #42:
score: 0
Accepted
time: 207ms
memory: 16416kb
input:
10 18052 18051 55715 55717 57933 57931 78574 78576 37241 37243 4851 4853 83373 83375 37863 37865 37892 37894 83822 83821
output:
36101 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 ...
result:
ok Ok
Test #43:
score: 0
Accepted
time: 134ms
memory: 13936kb
input:
10 2394 2392 24337 24339 55254 55256 46338 46339 11158 11159 20181 20182 59816 59818 15018 15020 39382 39381 33622 33623
output:
4783 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 1 -5 ...
result:
ok Ok
Test #44:
score: 0
Accepted
time: 187ms
memory: 17568kb
input:
10 13518 13517 67574 67576 76936 76938 73347 73349 7000 7001 19392 19391 6627 6626 24433 24432 98264 98265 94139 94141
output:
27033 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 ...
result:
ok Ok
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%