QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#426644 | #6320. Parallel Processing (Hard) | yzy1 | AC ✓ | 1ms | 3932kb | C++23 | 7.3kb | 2024-05-31 16:46:35 | 2024-05-31 16:46:36 |
Judging History
answer
#include <bits/stdc++.h>
#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>
#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 each(i, x) for (auto &&i : (x))
#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;
}
int n;
vector<array<int, 12>> Ans;
inline void Work(int l, int r) {
if (l == r) return;
if (r - l + 1 == 2) {
Ans.push_back({r, l, r});
return;
}
if (r - l + 1 == 3) {
Ans.push_back({l + 1, l, l + 1});
Ans.push_back({l + 2, l + 1, l + 2});
return;
}
if (r - l + 1 == 4) {
Ans.push_back({l + 1, l, l + 1, l + 2, l + 1, l + 2, l + 3, l + 2, l + 3});
Ans.push_back({l + 2, l, l + 2, l + 3, l + 1, l + 3});
return;
}
if (r - l + 1 == 5) {
Ans.push_back({l + 1, l, l + 1, l + 2, l + 1, l + 2, l + 3, l + 2, l + 3, l + 4, l + 3, l + 4});
Ans.push_back({l + 2, l, l + 2, l + 3, l + 1, l + 3});
Ans.push_back({l + 4, l + 2, l + 4});
return;
}
if (r - l + 1 == 6) {
Ans.push_back({l + 1, l, l + 1, l + 2, l + 1, l + 2, l + 3, l + 2, l + 3, l + 4, l + 3, l + 4});
Ans.push_back({l + 2, l, l + 2, l + 3, l + 1, l + 3, l + 5, l + 4, l + 5});
Ans.push_back({l + 4, l + 2, l + 4, l + 5, l + 2, l + 5});
return;
}
if (r - l + 1 == 7) {
Ans.push_back({l + 1, l, l + 1, l + 2, l + 1, l + 2, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5});
Ans.push_back({l + 2, l, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6});
Ans.push_back({l + 4, l + 3, l + 4, l + 5, l + 3, l + 5, l + 6, l + 3, l + 6});
return;
}
if (r - l + 1 == 8) {
Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 7, l + 6, l + 7});
Ans.push_back(
{l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 7, l + 5, l + 7});
Ans.push_back(
{l + 4, l + 3, l + 4, l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 7, l + 3, l + 7});
return;
}
if (r - l + 1 == 10) {
Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 7, l + 6, l + 7});
Ans.push_back(
{l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 7, l + 5, l + 7});
Ans.push_back(
{l + 4, l + 3, l + 4, l + 7, l + 3, l + 7, l + 8, l + 7, l + 8, l + 9, l + 8, l + 9});
Ans.push_back(
{l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 8, l + 3, l + 8, l + 9, l + 7, l + 9});
return;
}
if (r - l + 1 == 11) {
Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 8, l + 7, l + 8});
Ans.push_back(
{l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 9, l + 8, l + 9});
Ans.push_back(
{l + 4, l + 3, l + 4, l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 10, l + 9, l + 10});
Ans.push_back(
{l + 7, l + 6, l + 7, l + 8, l + 6, l + 8, l + 9, l + 6, l + 9, l + 10, l + 6, l + 10});
return;
}
if (r - l + 1 == 12) {
Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 7, l + 6, l + 7});
Ans.push_back(
{l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 7, l + 5, l + 7});
Ans.push_back(
{l + 4, l + 3, l + 4, l + 7, l + 3, l + 7, l + 8, l + 7, l + 8, l + 9, l + 8, l + 9});
Ans.push_back(
{l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 9, l + 7, l + 9, l + 11, l + 10, l + 11});
Ans.push_back({l + 8, l + 3, l + 8, l + 10, l + 9, l + 10, l + 11, l + 9, l + 11});
return;
}
if (r - l + 1 == 13) {
Ans.push_back({l + 1, l, l + 1, l + 3, l + 2, l + 3, l + 5, l + 4, l + 5, l + 7, l + 6, l + 7});
Ans.push_back(
{l + 2, l + 1, l + 2, l + 3, l + 1, l + 3, l + 6, l + 5, l + 6, l + 7, l + 5, l + 7});
Ans.push_back(
{l + 4, l + 3, l + 4, l + 7, l + 3, l + 7, l + 9, l + 8, l + 9, l + 11, l + 10, l + 11});
Ans.push_back(
{l + 5, l + 3, l + 5, l + 6, l + 3, l + 6, l + 9, l + 7, l + 9, l + 12, l + 11, l + 12});
Ans.push_back(
{l + 8, l + 7, l + 8, l + 10, l + 9, l + 10, l + 11, l + 9, l + 11, l + 12, l + 9, l + 12});
return;
}
Work(l, l + 7);
Work(l + 7, r);
}
deque<pair<int, int>> dq1, dq2;
signed main() {
// #ifndef LOCAL
// fio("cpu");
// #endif
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// int Test;
// cin >> Test;
cin >> n;
if (n <= 15) {
Work(1, n);
cout << Ans.size() << '\n';
for (auto a : Ans) {
rep (i, 0, 11) cout << (a[i] ?: 2000) << " \n"[i % 3 == 2];
}
exit(0);
}
int sz = max(4, n / 5);
// dbg(sz);
for (int j : {2, 3, 0})
rep (i, sz + 1, n)
if ((i - sz) % 4 == j) dq1.push_back({i, i - 1});
rep (i, 2, sz) {
pair<int, int> x1 = {2000, 2000}, x2 = {2000, 2000}, x3 = {2000, 2000};
if (dq1.size()) x1 = dq1.front(), dq1.pop_front();
if (dq1.size()) x2 = dq1.front(), dq1.pop_front();
if (dq1.size()) x3 = dq1.front(), dq1.pop_front();
Ans.push_back({i, i - 1, i, x1.first, x1.second, x1.first, x2.first, x2.second, x2.first,
x3.first, x3.second, x3.first});
}
ste (i, sz + 1, n, 4) {
if (i + 3 <= n) dq2.push_back({i + 3, i - 1});
dq2.push_back({i, i - 1});
if (i + 2 <= n) dq2.push_back({i + 2, i - 1});
if (i + 1 <= n) dq2.push_back({i + 1, i - 1});
}
while (dq1.size()) {
assert(dq2.size());
pair<int, int> x1 = dq2.front(), x2 = {2000, 2000}, x3 = {2000, 2000}, x4 = {2000, 2000};
dq2.pop_front();
if (dq1.size())
x2 = dq1.front(), dq1.pop_front();
else if (dq2.size())
x2 = dq2.front(), dq2.pop_front();
if (dq1.size())
x3 = dq1.front(), dq1.pop_front();
else if (dq2.size())
x3 = dq2.front(), dq2.pop_front();
if (dq1.size())
x4 = dq1.front(), dq1.pop_front();
else if (dq2.size())
x4 = dq2.front(), dq2.pop_front();
Ans.push_back({x1.first, x1.second, x1.first, x2.first, x2.second, x2.first, x3.first,
x3.second, x3.first, x4.first, x4.second, x4.first});
}
while (dq2.size()) {
pair<int, int> x1 = dq2.front(), x2 = {2000, 2000}, x3 = {2000, 2000}, x4 = {2000, 2000};
dq2.pop_front();
if (dq2.size()) x2 = dq2.front(), dq2.pop_front();
if (dq2.size()) x3 = dq2.front(), dq2.pop_front();
if (dq2.size()) x4 = dq2.front(), dq2.pop_front();
Ans.push_back({x1.first, x1.second, x1.first, x2.first, x2.second, x2.first, x3.first,
x3.second, x3.first, x4.first, x4.second, x4.first});
}
cout << Ans.size() << '\n';
for (auto a : Ans) {
rep (i, 0, 11) cout << (a[i] ?: 2000) << " \n"[i % 3 == 2];
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
input:
17
output:
7 2 1 2 6 5 6 10 9 10 14 13 14 3 2 3 7 6 7 11 10 11 15 14 15 4 3 4 8 7 8 12 11 12 16 15 16 8 4 8 5 4 5 7 4 7 6 4 6 12 8 12 9 8 9 11 8 11 10 8 10 16 12 16 13 12 13 15 12 15 14 12 14 17 16 17 2000 2000 2000 2000 2000 2000 2000 2000 2000
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
18
output:
7 2 1 2 6 5 6 10 9 10 14 13 14 3 2 3 18 17 18 7 6 7 11 10 11 4 3 4 15 14 15 8 7 8 12 11 12 8 4 8 16 15 16 5 4 5 7 4 7 6 4 6 12 8 12 9 8 9 11 8 11 10 8 10 16 12 16 13 12 13 15 12 15 14 12 14 17 16 17 18 16 18 2000 2000 2000
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
19
output:
8 2 1 2 6 5 6 10 9 10 14 13 14 3 2 3 18 17 18 7 6 7 11 10 11 4 3 4 15 14 15 19 18 19 8 7 8 8 4 8 12 11 12 16 15 16 5 4 5 7 4 7 6 4 6 12 8 12 9 8 9 11 8 11 10 8 10 16 12 16 13 12 13 15 12 15 14 12 14 17 16 17 19 16 19 18 16 18 2000 2000 2000 2000 2000 2000 2000 2000 2000
result:
ok AC
Test #4:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
20
output:
8 2 1 2 6 5 6 10 9 10 14 13 14 3 2 3 18 17 18 7 6 7 11 10 11 4 3 4 15 14 15 19 18 19 8 7 8 8 4 8 12 11 12 16 15 16 20 19 20 5 4 5 7 4 7 6 4 6 12 8 12 9 8 9 11 8 11 10 8 10 16 12 16 13 12 13 15 12 15 14 12 14 20 16 20 17 16 17 19 16 19 18 16 18 2000 2000 2000
result:
ok AC
Test #5:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
21
output:
8 2 1 2 6 5 6 10 9 10 14 13 14 3 2 3 18 17 18 7 6 7 11 10 11 4 3 4 15 14 15 19 18 19 8 7 8 8 4 8 12 11 12 16 15 16 20 19 20 5 4 5 7 4 7 6 4 6 12 8 12 9 8 9 11 8 11 10 8 10 16 12 16 13 12 13 15 12 15 14 12 14 20 16 20 17 16 17 19 16 19 18 16 18 21 20 21
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
120
output:
48 2 1 2 26 25 26 30 29 30 34 33 34 3 2 3 38 37 38 42 41 42 46 45 46 4 3 4 50 49 50 54 53 54 58 57 58 5 4 5 62 61 62 66 65 66 70 69 70 6 5 6 74 73 74 78 77 78 82 81 82 7 6 7 86 85 86 90 89 90 94 93 94 8 7 8 98 97 98 102 101 102 106 105 106 9 8 9 110 109 110 114 113 114 118 117 118 10 9 10 27 26 27 3...
result:
ok AC
Test #7:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
421
output:
168 2 1 2 86 85 86 90 89 90 94 93 94 3 2 3 98 97 98 102 101 102 106 105 106 4 3 4 110 109 110 114 113 114 118 117 118 5 4 5 122 121 122 126 125 126 130 129 130 6 5 6 134 133 134 138 137 138 142 141 142 7 6 7 146 145 146 150 149 150 154 153 154 8 7 8 158 157 158 162 161 162 166 165 166 9 8 9 170 169 ...
result:
ok AC
Test #8:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
464
output:
186 2 1 2 94 93 94 98 97 98 102 101 102 3 2 3 106 105 106 110 109 110 114 113 114 4 3 4 118 117 118 122 121 122 126 125 126 5 4 5 130 129 130 134 133 134 138 137 138 6 5 6 142 141 142 146 145 146 150 149 150 7 6 7 154 153 154 158 157 158 162 161 162 8 7 8 166 165 166 170 169 170 174 173 174 9 8 9 17...
result:
ok AC
Test #9:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
812
output:
325 2 1 2 164 163 164 168 167 168 172 171 172 3 2 3 176 175 176 180 179 180 184 183 184 4 3 4 188 187 188 192 191 192 196 195 196 5 4 5 200 199 200 204 203 204 208 207 208 6 5 6 212 211 212 216 215 216 220 219 220 7 6 7 224 223 224 228 227 228 232 231 232 8 7 8 236 235 236 240 239 240 244 243 244 9 ...
result:
ok AC
Test #10:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
862
output:
345 2 1 2 174 173 174 178 177 178 182 181 182 3 2 3 186 185 186 190 189 190 194 193 194 4 3 4 198 197 198 202 201 202 206 205 206 5 4 5 210 209 210 214 213 214 218 217 218 6 5 6 222 221 222 226 225 226 230 229 230 7 6 7 234 233 234 238 237 238 242 241 242 8 7 8 246 245 246 250 249 250 254 253 254 9 ...
result:
ok AC
Test #11:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
996
output:
398 2 1 2 201 200 201 205 204 205 209 208 209 3 2 3 213 212 213 217 216 217 221 220 221 4 3 4 225 224 225 229 228 229 233 232 233 5 4 5 237 236 237 241 240 241 245 244 245 6 5 6 249 248 249 253 252 253 257 256 257 7 6 7 261 260 261 265 264 265 269 268 269 8 7 8 273 272 273 277 276 277 281 280 281 9 ...
result:
ok AC
Test #12:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
997
output:
399 2 1 2 201 200 201 205 204 205 209 208 209 3 2 3 213 212 213 217 216 217 221 220 221 4 3 4 225 224 225 229 228 229 233 232 233 5 4 5 237 236 237 241 240 241 245 244 245 6 5 6 249 248 249 253 252 253 257 256 257 7 6 7 261 260 261 265 264 265 269 268 269 8 7 8 273 272 273 277 276 277 281 280 281 9 ...
result:
ok AC
Test #13:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
998
output:
399 2 1 2 201 200 201 205 204 205 209 208 209 3 2 3 213 212 213 217 216 217 221 220 221 4 3 4 225 224 225 229 228 229 233 232 233 5 4 5 237 236 237 241 240 241 245 244 245 6 5 6 249 248 249 253 252 253 257 256 257 7 6 7 261 260 261 265 264 265 269 268 269 8 7 8 273 272 273 277 276 277 281 280 281 9 ...
result:
ok AC
Test #14:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
999
output:
400 2 1 2 201 200 201 205 204 205 209 208 209 3 2 3 213 212 213 217 216 217 221 220 221 4 3 4 225 224 225 229 228 229 233 232 233 5 4 5 237 236 237 241 240 241 245 244 245 6 5 6 249 248 249 253 252 253 257 256 257 7 6 7 261 260 261 265 264 265 269 268 269 8 7 8 273 272 273 277 276 277 281 280 281 9 ...
result:
ok AC
Test #15:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
1000
output:
400 2 1 2 202 201 202 206 205 206 210 209 210 3 2 3 214 213 214 218 217 218 222 221 222 4 3 4 226 225 226 230 229 230 234 233 234 5 4 5 238 237 238 242 241 242 246 245 246 6 5 6 250 249 250 254 253 254 258 257 258 7 6 7 262 261 262 266 265 266 270 269 270 8 7 8 274 273 274 278 277 278 282 281 282 9 ...
result:
ok AC