QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#808771 | #8195. Satelity | ucup-team004 | 0 | 1ms | 3916kb | C++23 | 2.7kb | 2024-12-11 02:46:35 | 2024-12-11 02:46:36 |
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, p, M;
std::cin >> n >> p >> M;
std::vector g(n, std::vector<int>(n)), gT(n, std::vector<int>(n));
for (int i = 0; i < p; i++) {
int a, b;
std::cin >> a >> b;
a--;
b--;
b -= n;
g[a][b] = 1;
gT[b][a] = 1;
}
bool swapped = false;
int l = std::set(g.begin(), g.end()).size();
int r = std::set(gT.begin(), gT.end()).size();
if (l > r) {
std::swap(l, r);
std::swap(g, gT);
swapped = true;
}
std::map<std::vector<int>, std::vector<int>> vec;
std::map<std::vector<int>, std::vector<int>> vecb;
for (int i = 0; i < n; i++) {
vec[g[i]].push_back(i);
vecb[gT[i]].push_back(i);
}
std::vector<std::string> ans(2 * n);
int maxa = 0, maxb = 0;
for (const auto &[b, a] : vec) {
for (int i = 0; i < n; i++) {
ans[i] += 'A';
ans[n + i] += 'B';
}
for (auto i : a) {
ans[i].back() = 'C';
}
for (int i = 0; i < n; i++) {
if (b[i]) {
ans[n + i].back() = 'C';
}
}
maxa = std::max(maxa, int(a.size()));
}
for (const auto &[a, b] : vecb) {
maxb = std::max(maxb, int(b.size()));
}
int ka = std::__lg(2 * maxa - 1);
int kb = std::__lg(2 * maxb - 1);
for (int i = 0; i < ka; i++) {
for (int i = 0; i < n; i++) {
ans[i] += 'A';
ans[n + i] += 'B';
}
for (const auto &[b, a] : vec) {
for (int j = 0; j < a.size(); j++) {
if (j >> i & 1) {
ans[a[j]].back() = 'C';
}
}
}
}
for (int i = 0; i < kb; i++) {
for (int i = 0; i < n; i++) {
ans[i] += 'A';
ans[n + i] += 'B';
}
for (const auto &[a, b] : vecb) {
for (int j = 0; j < b.size(); j++) {
if (j >> i & 1) {
ans[b[j]].back() = 'C';
}
}
}
}
if (r == n) {
for (int i = 0; i < n; i++) {
ans[i] += 'A';
ans[n + i] += 'B';
}
}
if (swapped) {
std::rotate(ans.begin(), ans.begin() + n, ans.end());
}
std::cout << ans[0].size() << "\n";
for (const auto &s : ans) {
std::cout << s << "\n";
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 0ms
memory: 3856kb
input:
100 5340 10200 1 101 1 102 1 104 1 105 1 106 1 107 1 108 1 109 1 116 1 119 1 120 1 123 1 125 1 126 1 127 1 129 1 132 1 133 1 135 1 136 1 137 1 138 1 141 1 144 1 146 1 147 1 148 1 149 1 151 1 155 1 156 1 158 1 159 1 160 1 161 1 163 1 165 1 167 1 168 1 169 1 170 1 172 1 173 1 174 1 175 1 177 1 178 1 1...
output:
101 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
result:
ok correct
Test #2:
score: 7
Accepted
time: 1ms
memory: 3740kb
input:
100 658 10200 1 104 1 148 1 169 1 175 1 177 1 181 1 187 1 188 2 132 2 190 3 119 3 147 3 154 3 163 3 165 3 177 3 184 3 199 4 102 4 105 4 130 4 132 4 138 4 160 4 183 4 192 4 199 5 113 5 152 5 153 5 165 5 186 5 194 6 111 6 114 6 134 6 155 6 199 7 109 7 120 7 128 7 131 7 136 7 143 7 191 8 104 8 107 8 17...
output:
101 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
result:
ok correct
Test #3:
score: 7
Accepted
time: 1ms
memory: 3776kb
input:
100 9540 10200 1 101 1 102 1 103 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 115 1 116 1 117 1 118 1 119 1 120 1 121 1 122 1 123 1 124 1 125 1 126 1 127 1 128 1 129 1 131 1 132 1 133 1 134 1 135 1 136 1 137 1 138 1 139 1 140 1 141 1 142 1 143 1 144 1 145 1 146 1 147 1 148 1 1...
output:
101 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
result:
ok correct
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 3916kb
input:
100 10000 10200 1 101 1 102 1 103 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 115 1 116 1 117 1 118 1 119 1 120 1 121 1 122 1 123 1 124 1 125 1 126 1 127 1 128 1 129 1 130 1 131 1 132 1 133 1 134 1 135 1 136 1 137 1 138 1 139 1 140 1 141 1 142 1 143 1 144 1 145 1 146 1 147 1 ...
output:
15 CAAAAAAAAAAAAAA CCAAAAAACAAAAAA CACAAAAAACAAAAA CCCAAAAACCAAAAA CAACAAAAAACAAAA CCACAAAACACAAAA CACCAAAAACCAAAA CCCCAAAACCCAAAA CAAACAAAAAACAAA CCAACAAACAACAAA CACACAAAACACAAA CCCACAAACCACAAA CAACCAAAAACCAAA CCACCAAACACCAAA CACCCAAAACCCAAA CCCCCAAACCCCAAA CAAAACAAAAAACAA CCAAACAACAAACAA CACAACAAA...
result:
wrong answer some tokens appeared more than once
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%