QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#353980#8310. Fixing NetworksPlentyOfPenalty#AC ✓16ms11304kbC++202.2kb2024-03-14 20:10:112024-03-14 20:10:12

Judging History

你现在查看的是最新测评结果

  • [2024-03-14 20:10:12]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:11304kb
  • [2024-03-14 20:10:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, d, c;
vector<int> G[N];
vector<int> nod[N];
vector<pair<int, int>> ans;
bool solve(vector<int> &a) {
  int m = a.size();
  if (m == 0) return false;
  if (d & 1) {
    if (m / 2 <= d / 2) return false;
    assert(m % 2 == 0);
    for (int i = 0; i < m; i++) {
      for (int j = 1; j <= d / 2; j++) {
        ans.emplace_back(a[i], a[(i + j) % m]);
      }
    }
    for (int i = 0; i < m / 2; i++) {
      ans.emplace_back(a[i], a[i + m / 2]);
    }
  } else {
    if (m <= d) {
      return false;
    }
    for (int i = 0; i < m; i++) {
      for (int j = 1; j <= d / 2; j++) {
        ans.emplace_back(a[i], a[(i + j) % m]);
      }
    }
  }
  return true;
}
bool solve() {
  if (d == 0) {
    return n == c;
  } else if (d == 1) {
    if (n % 2 == 0 && n / 2 == c) {
      for (int i = 1; i <= n; i += 2) {
        ans.emplace_back(i, i + 1);
      }
      return true;
    } else {
      return false;
    }
  }
  if (n % 2 == 1 && d % 2 == 1) {
    return false;
  }
  int m = n / c, tot = 0;
  if (d % 2 == 0) {
    for (int i = 1; i <= n % c; i++) {
      nod[i].push_back(++tot);
    }
  } else {
    m = (m >> 1) << 1;
    for (int i = 1; i <= (n - m * c) / 2; i++) {
      nod[i].push_back(++tot);
      nod[i].push_back(++tot);
    }
  }
  for (int i = 1; i <= c; i++) {
    for (int j = 1; j <= m; j++) nod[i].push_back(++tot);
  }
  assert(tot == n);
  for (int i = 1; i <= c; i++)
    if (!solve(nod[i])) {
      return false;
    }
  return true;
}
int main() {
#ifdef memset0
  freopen("F.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> d >> c;
  bool found = solve();
  if (found) {
    cout << "Yes" << endl;
    for (const auto &[u, v] : ans) {
      // cout << u << ' ' << v << '\n';
      G[u].push_back(v);
      G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
      sort(G[i].begin(), G[i].end());
      for (int x : G[i]) cout << x << ' ';
      cout << '\n';
      assert(G[i].size() == d);
      for (int j = 1; j < G[i].size(); j++) assert(G[i][j] != G[i][j - 1]);
    }
  } else {
    cout << "No" << endl;
  }
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3652kb

input:

12 3 2

output:

Yes
2 4 6 
1 3 5 
2 4 6 
1 3 5 
2 4 6 
1 3 5 
8 10 12 
7 9 11 
8 10 12 
7 9 11 
8 10 12 
7 9 11 

result:

ok n=12 d=3 c=2

Test #2:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

3 2 2

output:

No

result:

ok n=3 d=2 c=2

Test #3:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

1 0 1

output:

Yes


result:

ok n=1 d=0 c=1

Test #4:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

2 0 1

output:

No

result:

ok n=2 d=0 c=1

Test #5:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

2 0 2

output:

Yes



result:

ok n=2 d=0 c=2

Test #6:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

3 0 2

output:

No

result:

ok n=3 d=0 c=2

Test #7:

score: 0
Accepted
time: 2ms
memory: 3628kb

input:

100000 0 100000

output:

Yes








































































































































































































































































































...

result:

ok n=100000 d=0 c=100000

Test #8:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

2 1 1

output:

Yes
2 
1 

result:

ok n=2 d=1 c=1

Test #9:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

2 1 2

output:

No

result:

ok n=2 d=1 c=2

Test #10:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

3 1 1

output:

No

result:

ok n=3 d=1 c=1

Test #11:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

3 1 2

output:

No

result:

ok n=3 d=1 c=2

Test #12:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

3 1 3

output:

No

result:

ok n=3 d=1 c=3

Test #13:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

4 1 1

output:

No

result:

ok n=4 d=1 c=1

Test #14:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

4 1 2

output:

Yes
2 
1 
4 
3 

result:

ok n=4 d=1 c=2

Test #15:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

4 1 3

output:

No

result:

ok n=4 d=1 c=3

Test #16:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

4 1 4

output:

No

result:

ok n=4 d=1 c=4

Test #17:

score: 0
Accepted
time: 7ms
memory: 9076kb

input:

100000 1 50000

output:

Yes
2 
1 
4 
3 
6 
5 
8 
7 
10 
9 
12 
11 
14 
13 
16 
15 
18 
17 
20 
19 
22 
21 
24 
23 
26 
25 
28 
27 
30 
29 
32 
31 
34 
33 
36 
35 
38 
37 
40 
39 
42 
41 
44 
43 
46 
45 
48 
47 
50 
49 
52 
51 
54 
53 
56 
55 
58 
57 
60 
59 
62 
61 
64 
63 
66 
65 
68 
67 
70 
69 
72 
71 
74 
73 
76 
75 
7...

result:

ok n=100000 d=1 c=50000

Test #18:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

3 2 1

output:

Yes
2 3 
1 3 
1 2 

result:

ok n=3 d=2 c=1

Test #19:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

4 2 1

output:

Yes
2 4 
1 3 
2 4 
1 3 

result:

ok n=4 d=2 c=1

Test #20:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

6 2 1

output:

Yes
2 6 
1 3 
2 4 
3 5 
4 6 
1 5 

result:

ok n=6 d=2 c=1

Test #21:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

6 2 2

output:

Yes
2 3 
1 3 
1 2 
5 6 
4 6 
4 5 

result:

ok n=6 d=2 c=2

Test #22:

score: 0
Accepted
time: 12ms
memory: 9864kb

input:

100000 2 1

output:

Yes
2 100000 
1 3 
2 4 
3 5 
4 6 
5 7 
6 8 
7 9 
8 10 
9 11 
10 12 
11 13 
12 14 
13 15 
14 16 
15 17 
16 18 
17 19 
18 20 
19 21 
20 22 
21 23 
22 24 
23 25 
24 26 
25 27 
26 28 
27 29 
28 30 
29 31 
30 32 
31 33 
32 34 
33 35 
34 36 
35 37 
36 38 
37 39 
38 40 
39 41 
40 42 
41 43 
42 44 
43 45 
4...

result:

ok n=100000 d=2 c=1

Test #23:

score: 0
Accepted
time: 11ms
memory: 10072kb

input:

100000 2 316

output:

Yes
145 460 
461 776 
777 1092 
1093 1408 
1409 1724 
1725 2040 
2041 2356 
2357 2672 
2673 2988 
2989 3304 
3305 3620 
3621 3936 
3937 4252 
4253 4568 
4569 4884 
4885 5200 
5201 5516 
5517 5832 
5833 6148 
6149 6464 
6465 6780 
6781 7096 
7097 7412 
7413 7728 
7729 8044 
8045 8360 
8361 8676 
8677...

result:

ok n=100000 d=2 c=316

Test #24:

score: 0
Accepted
time: 16ms
memory: 11304kb

input:

100000 2 33333

output:

Yes
2 4 
1 3 
2 4 
1 3 
6 7 
5 7 
5 6 
9 10 
8 10 
8 9 
12 13 
11 13 
11 12 
15 16 
14 16 
14 15 
18 19 
17 19 
17 18 
21 22 
20 22 
20 21 
24 25 
23 25 
23 24 
27 28 
26 28 
26 27 
30 31 
29 31 
29 30 
33 34 
32 34 
32 33 
36 37 
35 37 
35 36 
39 40 
38 40 
38 39 
42 43 
41 43 
41 42 
45 46 
44 46 ...

result:

ok n=100000 d=2 c=33333

Test #25:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

4 3 1

output:

Yes
2 3 4 
1 3 4 
1 2 4 
1 2 3 

result:

ok n=4 d=3 c=1

Test #26:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

4 3 2

output:

No

result:

ok n=4 d=3 c=2

Test #27:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

8 3 1

output:

Yes
2 5 8 
1 3 6 
2 4 7 
3 5 8 
1 4 6 
2 5 7 
3 6 8 
1 4 7 

result:

ok n=8 d=3 c=1

Test #28:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

8 3 2

output:

Yes
2 3 4 
1 3 4 
1 2 4 
1 2 3 
6 7 8 
5 7 8 
5 6 8 
5 6 7 

result:

ok n=8 d=3 c=2

Test #29:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

9 3 1

output:

No

result:

ok n=9 d=3 c=1

Test #30:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

9 3 2

output:

No

result:

ok n=9 d=3 c=2

Test #31:

score: 0
Accepted
time: 15ms
memory: 7912kb

input:

66666 3 1

output:

Yes
2 33334 66666 
1 3 33335 
2 4 33336 
3 5 33337 
4 6 33338 
5 7 33339 
6 8 33340 
7 9 33341 
8 10 33342 
9 11 33343 
10 12 33344 
11 13 33345 
12 14 33346 
13 15 33347 
14 16 33348 
15 17 33349 
16 18 33350 
17 19 33351 
18 20 33352 
19 21 33353 
20 22 33354 
21 23 33355 
22 24 33356 
23 25 33357...

result:

ok n=66666 d=3 c=1

Test #32:

score: 0
Accepted
time: 12ms
memory: 8628kb

input:

66666 3 16666

output:

Yes
2 4 6 
1 3 5 
2 4 6 
1 3 5 
2 4 6 
1 3 5 
8 9 10 
7 9 10 
7 8 10 
7 8 9 
12 13 14 
11 13 14 
11 12 14 
11 12 13 
16 17 18 
15 17 18 
15 16 18 
15 16 17 
20 21 22 
19 21 22 
19 20 22 
19 20 21 
24 25 26 
23 25 26 
23 24 26 
23 24 25 
28 29 30 
27 29 30 
27 28 30 
27 28 29 
32 33 34 
31 33 34 
31 ...

result:

ok n=66666 d=3 c=16666

Test #33:

score: 0
Accepted
time: 9ms
memory: 6196kb

input:

20000 10 1

output:

Yes
2 3 4 5 6 19996 19997 19998 19999 20000 
1 3 4 5 6 7 19997 19998 19999 20000 
1 2 4 5 6 7 8 19998 19999 20000 
1 2 3 5 6 7 8 9 19999 20000 
1 2 3 4 6 7 8 9 10 20000 
1 2 3 4 5 7 8 9 10 11 
2 3 4 5 6 8 9 10 11 12 
3 4 5 6 7 9 10 11 12 13 
4 5 6 7 8 10 11 12 13 14 
5 6 7 8 9 11 12 13 14 15 
6 7 8 ...

result:

ok n=20000 d=10 c=1

Test #34:

score: 0
Accepted
time: 12ms
memory: 6212kb

input:

20000 10 100

output:

Yes
2 3 4 5 6 196 197 198 199 200 
1 3 4 5 6 7 197 198 199 200 
1 2 4 5 6 7 8 198 199 200 
1 2 3 5 6 7 8 9 199 200 
1 2 3 4 6 7 8 9 10 200 
1 2 3 4 5 7 8 9 10 11 
2 3 4 5 6 8 9 10 11 12 
3 4 5 6 7 9 10 11 12 13 
4 5 6 7 8 10 11 12 13 14 
5 6 7 8 9 11 12 13 14 15 
6 7 8 9 10 12 13 14 15 16 
7 8 9 10 ...

result:

ok n=20000 d=10 c=100

Test #35:

score: 0
Accepted
time: 4ms
memory: 6348kb

input:

20000 10 1818

output:

Yes
3 4 5 6 7 9 10 11 12 13 
14 15 16 17 18 20 21 22 23 24 
1 4 5 6 7 8 10 11 12 13 
1 3 5 6 7 8 9 11 12 13 
1 3 4 6 7 8 9 10 12 13 
1 3 4 5 7 8 9 10 11 13 
1 3 4 5 6 8 9 10 11 12 
3 4 5 6 7 9 10 11 12 13 
1 4 5 6 7 8 10 11 12 13 
1 3 5 6 7 8 9 11 12 13 
1 3 4 6 7 8 9 10 12 13 
1 3 4 5 7 8 9 10 11 1...

result:

ok n=20000 d=10 c=1818

Test #36:

score: 0
Accepted
time: 9ms
memory: 5860kb

input:

18180 11 1

output:

Yes
2 3 4 5 6 9091 18176 18177 18178 18179 18180 
1 3 4 5 6 7 9092 18177 18178 18179 18180 
1 2 4 5 6 7 8 9093 18178 18179 18180 
1 2 3 5 6 7 8 9 9094 18179 18180 
1 2 3 4 6 7 8 9 10 9095 18180 
1 2 3 4 5 7 8 9 10 11 9096 
2 3 4 5 6 8 9 10 11 12 9097 
3 4 5 6 7 9 10 11 12 13 9098 
4 5 6 7 8 10 11 12...

result:

ok n=18180 d=11 c=1

Test #37:

score: 0
Accepted
time: 8ms
memory: 5944kb

input:

18180 11 100

output:

Yes
2 181 182 183 184 270 356 357 358 359 360 
1 181 182 183 184 185 271 357 358 359 360 
4 361 362 363 364 450 536 537 538 539 540 
3 361 362 363 364 365 451 537 538 539 540 
6 541 542 543 544 630 716 717 718 719 720 
5 541 542 543 544 545 631 717 718 719 720 
8 721 722 723 724 810 896 897 898 899 ...

result:

ok n=18180 d=11 c=100

Test #38:

score: 0
Accepted
time: 8ms
memory: 6080kb

input:

18180 11 1515

output:

Yes
2 3 4 5 6 7 8 9 10 11 12 
1 3 4 5 6 7 8 9 10 11 12 
1 2 4 5 6 7 8 9 10 11 12 
1 2 3 5 6 7 8 9 10 11 12 
1 2 3 4 6 7 8 9 10 11 12 
1 2 3 4 5 7 8 9 10 11 12 
1 2 3 4 5 6 8 9 10 11 12 
1 2 3 4 5 6 7 9 10 11 12 
1 2 3 4 5 6 7 8 10 11 12 
1 2 3 4 5 6 7 8 9 11 12 
1 2 3 4 5 6 7 8 9 10 12 
1 2 3 4 5 6 ...

result:

ok n=18180 d=11 c=1515

Test #39:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

101 100 1

output:

Yes
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 90 91 92 93 94 95 96 97 98 99 100 101 
1...

result:

ok n=101 d=100 c=1

Test #40:

score: 0
Accepted
time: 10ms
memory: 5016kb

input:

2000 100 10

output:

Yes
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 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 18...

result:

ok n=2000 d=100 c=10

Test #41:

score: 0
Accepted
time: 7ms
memory: 5032kb

input:

2000 100 19

output:

Yes
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 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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 1...

result:

ok n=2000 d=100 c=19

Test #42:

score: 0
Accepted
time: 10ms
memory: 5032kb

input:

1980 101 1

output:

Yes
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 991 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 ...

result:

ok n=1980 d=101 c=1

Test #43:

score: 0
Accepted
time: 3ms
memory: 5060kb

input:

1980 101 10

output:

Yes
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 100 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 18...

result:

ok n=1980 d=101 c=10

Test #44:

score: 0
Accepted
time: 10ms
memory: 5136kb

input:

1980 101 19

output:

Yes
2 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 56 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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 10...

result:

ok n=1980 d=101 c=19

Test #45:

score: 0
Accepted
time: 10ms
memory: 5052kb

input:

447 446 1

output:

Yes
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 90 91 92 93 94 95 96 97 98 99 100 101 10...

result:

ok n=447 d=446 c=1

Extra Test:

score: 0
Extra Test Passed