QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#682140 | #8310. Fixing Networks | lhw# | AC ✓ | 15ms | 8676kb | C++14 | 1.8kb | 2024-10-27 14:06:28 | 2024-10-27 14:06:30 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<array>
#include<random>
#include<string>
#include<time.h>
#include<cstring>
#include<set>
#include<cmath>
#include<queue>
#define int long long
#define endl '\n'
#define F first
#define S second
#define sz size()
#define ln cout<<'\n'
#define B begin()
#define pb push_back
#define D end()
#define pii pair<int,int>
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e9;
int n, d, c;
void solve()
{
cin >> n >> d >> c;
vector<vector<int>> g(n + 1);
if ((d + 1) * c > n ){
cout << "No" << endl;
return;
}
if (n != c && d == 0)
{
cout << "No" << endl;
return;
}
if (n == c && d == 0)
{
cout << "Yes" << endl;
return;
}
if (d == 1)
{
if (n != c * 2) {
cout << "No" << endl;
return;
}
}
int k = n - (d + 1) * (c - 1);
for (int i = 1; i < k; i++)
{
g[i].push_back(i % k + 1);
g[i % k + 1].push_back(i);
}
int cnt;
cnt = k;
for (int i = 1; i <= k; i++)
{
while (g[i].size() < d)
{
if (cnt <= i+1)cnt = k;
//cout << i << ' ' << cnt << endl;
g[i].push_back(cnt);
g[cnt].push_back(i);
cnt--;
}
}
for (int i = 1; i <= k; i++)
{
if (g[i].size() != d) {
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
for (int i = 1; i <= k; i++)
{
sort(g[i].begin(), g[i].end());
for (int v : g[i])cout << v << ' ';
cout << endl;
}
for (int i = 1; i < c; i++)
{
for (int j = k + 1; j <= k + 1 + d; j++)
{
for (int kk = k+1; kk <= k + 1 + d; kk++)
{
if (kk == j)continue;
else cout << kk << ' ';
}
cout << endl;
}
k =k+ d + 1;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int tc = 1;
tc = 1;
while (tc--)
{
solve();
}
//cout<<"dafc";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
input:
12 3 2
output:
Yes 2 7 8 1 3 6 2 4 5 3 5 8 3 4 6 2 5 7 1 6 8 1 4 7 10 11 12 9 11 12 9 10 12 9 10 11
result:
ok n=12 d=3 c=2
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 2 2
output:
No
result:
ok n=3 d=2 c=2
Test #3:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
1 0 1
output:
Yes
result:
ok n=1 d=0 c=1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
2 0 1
output:
No
result:
ok n=2 d=0 c=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
2 0 2
output:
Yes
result:
ok n=2 d=0 c=2
Test #6:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 0 2
output:
No
result:
ok n=3 d=0 c=2
Test #7:
score: 0
Accepted
time: 0ms
memory: 5432kb
input:
100000 0 100000
output:
Yes
result:
ok n=100000 d=0 c=100000
Test #8:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 1 1
output:
Yes 2 1
result:
ok n=2 d=1 c=1
Test #9:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 1 2
output:
No
result:
ok n=2 d=1 c=2
Test #10:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 1 1
output:
No
result:
ok n=3 d=1 c=1
Test #11:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 1 2
output:
No
result:
ok n=3 d=1 c=2
Test #12:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 1 3
output:
No
result:
ok n=3 d=1 c=3
Test #13:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 1 1
output:
No
result:
ok n=4 d=1 c=1
Test #14:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 1 2
output:
Yes 2 1 4 3
result:
ok n=4 d=1 c=2
Test #15:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
4 1 3
output:
No
result:
ok n=4 d=1 c=3
Test #16:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
4 1 4
output:
No
result:
ok n=4 d=1 c=4
Test #17:
score: 0
Accepted
time: 6ms
memory: 5424kb
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: 0ms
memory: 3588kb
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: 0ms
memory: 3616kb
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: 3852kb
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: 3496kb
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: 14ms
memory: 8676kb
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: 9ms
memory: 8600kb
input:
100000 2 316
output:
Yes 2 99055 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 44...
result:
ok n=100000 d=2 c=316
Test #24:
score: 0
Accepted
time: 9ms
memory: 5432kb
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: 0ms
memory: 3620kb
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: 0ms
memory: 3588kb
input:
4 3 2
output:
No
result:
ok n=4 d=3 c=2
Test #27:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
8 3 1
output:
Yes 2 7 8 1 3 6 2 4 5 3 5 8 3 4 6 2 5 7 1 6 8 1 4 7
result:
ok n=8 d=3 c=1
Test #28:
score: 0
Accepted
time: 0ms
memory: 3848kb
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: 0ms
memory: 3496kb
input:
9 3 1
output:
No
result:
ok n=9 d=3 c=1
Test #30:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
9 3 2
output:
No
result:
ok n=9 d=3 c=2
Test #31:
score: 0
Accepted
time: 15ms
memory: 7956kb
input:
66666 3 1
output:
Yes 2 66665 66666 1 3 66664 2 4 66663 3 5 66662 4 6 66661 5 7 66660 6 8 66659 7 9 66658 8 10 66657 9 11 66656 10 12 66655 11 13 66654 12 14 66653 13 15 66652 14 16 66651 15 17 66650 16 18 66649 17 19 66648 18 20 66647 19 21 66646 20 22 66645 21 23 66644 22 24 66643 23 25 66642...
result:
ok n=66666 d=3 c=1
Test #32:
score: 0
Accepted
time: 8ms
memory: 4788kb
input:
66666 3 16666
output:
Yes 2 5 6 1 3 4 2 4 6 2 3 5 1 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: 12ms
memory: 6928kb
input:
20000 10 1
output:
Yes 2 19992 19993 19994 19995 19996 19997 19998 19999 20000 1 3 19984 19985 19986 19987 19988 19989 19990 19991 2 4 19976 19977 19978 19979 19980 19981 19982 19983 3 5 19968 19969 19970 19971 19972 19973 19974 19975 4 6 19960 19961 19962 19963 19964 19965 19966 19967 5 7 19952 19953 19954 19955...
result:
ok n=20000 d=10 c=1
Test #34:
score: 0
Accepted
time: 12ms
memory: 6468kb
input:
20000 10 100
output:
Yes 2 18903 18904 18905 18906 18907 18908 18909 18910 18911 1 3 18895 18896 18897 18898 18899 18900 18901 18902 2 4 18887 18888 18889 18890 18891 18892 18893 18894 3 5 18879 18880 18881 18882 18883 18884 18885 18886 4 6 18871 18872 18873 18874 18875 18876 18877 18878 5 7 18863 18864 18865 18866...
result:
ok n=20000 d=10 c=100
Test #35:
score: 0
Accepted
time: 8ms
memory: 3860kb
input:
20000 10 1818
output:
Yes 2 5 6 7 8 9 10 11 12 13 1 3 4 7 8 9 10 11 12 13 2 4 5 6 8 9 10 11 12 13 2 3 5 6 7 9 10 11 12 13 1 3 4 6 7 8 10 11 12 13 1 3 4 5 7 8 9 11 12 13 1 2 4 5 6 8 9 10 12 13 1 2 3 5 6 7 9 10 11 13 1 2 3 4 6 7 8 10 11 12 1 2 3 4 5 7 8 9 11 13 1 2 3 4 5 6 8 9 10 12 1 2 3 4 5 6 7 9 11 13 1 2 3 ...
result:
ok n=20000 d=10 c=1818
Test #36:
score: 0
Accepted
time: 12ms
memory: 6204kb
input:
18180 11 1
output:
Yes 2 18171 18172 18173 18174 18175 18176 18177 18178 18179 18180 1 3 18162 18163 18164 18165 18166 18167 18168 18169 18170 2 4 18153 18154 18155 18156 18157 18158 18159 18160 18161 3 5 18144 18145 18146 18147 18148 18149 18150 18151 18152 4 6 18135 18136 18137 18138 18139 18140 18141 18142 1814...
result:
ok n=18180 d=11 c=1
Test #37:
score: 0
Accepted
time: 8ms
memory: 6284kb
input:
18180 11 100
output:
Yes 2 16983 16984 16985 16986 16987 16988 16989 16990 16991 16992 1 3 16974 16975 16976 16977 16978 16979 16980 16981 16982 2 4 16965 16966 16967 16968 16969 16970 16971 16972 16973 3 5 16956 16957 16958 16959 16960 16961 16962 16963 16964 4 6 16947 16948 16949 16950 16951 16952 16953 16954 1695...
result:
ok n=18180 d=11 c=100
Test #38:
score: 0
Accepted
time: 8ms
memory: 3576kb
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: 1ms
memory: 3692kb
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: 9ms
memory: 4788kb
input:
2000 100 10
output:
Yes 2 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1...
result:
ok n=2000 d=100 c=10
Test #41:
score: 0
Accepted
time: 7ms
memory: 3884kb
input:
2000 100 19
output:
Yes 2 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 16...
result:
ok n=2000 d=100 c=19
Test #42:
score: 0
Accepted
time: 7ms
memory: 5532kb
input:
1980 101 1
output:
Yes 2 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939...
result:
ok n=1980 d=101 c=1
Test #43:
score: 0
Accepted
time: 6ms
memory: 4536kb
input:
1980 101 10
output:
Yes 2 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1...
result:
ok n=1980 d=101 c=10
Test #44:
score: 0
Accepted
time: 7ms
memory: 3852kb
input:
1980 101 19
output:
Yes 2 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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 1...
result:
ok n=1980 d=101 c=19
Test #45:
score: 0
Accepted
time: 8ms
memory: 5036kb
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