QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #426646 | #6319. Parallel Processing (Easy) | yzy1 | AC ✓ | 0ms | 3848kb | C++23 | 7.3kb | 2024-05-31 16:48:05 | 2024-05-31 16:48:05 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
input:
2
output:
1 2 1 2 2000 2000 2000 2000 2000 2000 2000 2000 2000
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
4
output:
2 2 1 2 3 2 3 4 3 4 2000 2000 2000 3 1 3 4 2 4 2000 2000 2000 2000 2000 2000
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
3
output:
2 2 1 2 2000 2000 2000 2000 2000 2000 2000 2000 2000 3 2 3 2000 2000 2000 2000 2000 2000 2000 2000 2000
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
5
output:
3 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 2000 2000 2000 2000 2000 2000 5 3 5 2000 2000 2000 2000 2000 2000 2000 2000 2000
result:
ok AC
Test #5:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
6
output:
3 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 6 5 6 2000 2000 2000 5 3 5 6 3 6 2000 2000 2000 2000 2000 2000
result:
ok AC
Test #6:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
7
output:
3 2 1 2 3 2 3 4 3 4 6 5 6 3 1 3 4 2 4 7 6 7 2000 2000 2000 5 4 5 6 4 6 7 4 7 2000 2000 2000
result:
ok AC
Test #7:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
8
output:
3 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8
result:
ok AC
Test #8:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
9
output:
4 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8 9 8 9 2000 2000 2000 2000 2000 2000 2000 2000 2000
result:
ok AC
Test #9:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
10
output:
4 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 8 4 8 9 8 9 10 9 10 6 4 6 7 4 7 9 4 9 10 8 10
result:
ok AC
Test #10:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
11
output:
4 2 1 2 4 3 4 6 5 6 9 8 9 3 2 3 4 2 4 7 6 7 10 9 10 5 4 5 6 4 6 7 4 7 11 10 11 8 7 8 9 7 9 10 7 10 11 7 11
result:
ok AC
Test #11:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
12
output:
5 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 8 4 8 9 8 9 10 9 10 6 4 6 7 4 7 10 8 10 12 11 12 9 4 9 11 10 11 12 10 12 2000 2000 2000
result:
ok AC
Test #12:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
13
output:
5 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 8 4 8 10 9 10 12 11 12 6 4 6 7 4 7 10 8 10 13 12 13 9 8 9 11 10 11 12 10 12 13 10 13
result:
ok AC
Test #13:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
14
output:
6 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8 9 8 9 10 9 10 11 10 11 13 12 13 10 8 10 11 9 11 14 13 14 2000 2000 2000 12 11 12 13 11 13 14 11 14 2000 2000 2000
result:
ok AC
Test #14:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
15
output:
6 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8 9 8 9 11 10 11 13 12 13 15 14 15 10 9 10 11 9 11 14 13 14 15 13 15 12 11 12 13 11 13 14 11 14 15 11 15
result:
ok AC
Test #15:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
16
output:
6 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
result:
ok AC