QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333531 | #5583. Color Tubes | joelgun14# | WA | 0ms | 3780kb | C++14 | 4.0kb | 2024-02-20 06:08:21 | 2024-02-20 06:08:22 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
const int N = 2e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector <vector <int>> a(n + 1);
vector <pair <int, int>> ans;
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 3; j++) {
int x; cin >> x;
if (x > 0) {
a[i].push_back(x);
}
}
}
for (int i = 0; i < n; i++) {
int j = i + 1;
while (a[i].size() < 3) {
while (a[j].size() == 0)
j++;
ans.push_back({j, i});
a[i].push_back(a[j].back());
a[j].pop_back();
}
assert(a[i].size() == 3);
}
assert(a[n].size() == 0);
auto print = [&]() {
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 3; j++) {
cerr << ((j < (int) a[i].size()) ? a[i][j] : 0) << " ";
}
cerr << "\n";
}
cerr << "\n";
};
auto move = [&](int i, int j) {
ans.push_back({i, j});
a[j].push_back(a[i].back());
a[i].pop_back();
};
vector <bool> done(n + 1);
for (int rep = 0; rep + 1 < n; rep++) {
// cerr << rep << "\n";
vector <int> sum(n + 1);
int free = 0;
for (int i = 0; i <= n; i++) if (!done[i]) {
if (a[i].size() == 0) {
free = i;
} else {
for (int j = 0; j < 3; j++)
sum[a[i][j]] += 3 - j;
}
}
vector <int> s;
int fir = 0;
while (done[fir] || fir == free || sum[a[fir].back()] >= 7) {
// cerr << '.';
fir++;
}
s.push_back(fir);
move(fir, free);
for (int i = 0; i <= n; i++) if (i != free && a[i].back() == a[free].back()) {
move(i, free);
s.push_back(i);
break;
}
if (a[free].size() == 1) {
for (int i = 0; i <= n; i++) if (a[i][1] == a[free].back()) {
move(i, s.back());
s.pop_back();
move(i, free);
s.push_back(i);
s.push_back(i);
break;
}
}
for (int i = 0; i <= n; i++) if (i != free) {
int found = false;
for (int j = 0; j < (int) a[i].size(); j++) {
if (a[i][j] == a[free].back()) {
found = true;
}
}
if (found) {
while (a[i].back() != a[free].back()) {
// cerr << a[free].back();
for (int j = 0; j < 2; j++) {
if (s[j] != i) {
move(i, s[j]);
s[j] = i;
break;
}
}
}
move(i, free);
s.push_back(i);
break;
}
}
sort(ALL(s));
done[free] = true;
if (s[0] == s[2])
continue;
if (s[0] == s[1]) {
move(s[0], s[2]);
} else if (s[1] == s[2]) {
move(s[2], s[0]);
} else {
move(s[0], s[2]);
move(s[0], s[1]);
}
// print();
}
cout << ans.size() << "\n";
for (auto &[x, y] : ans) {
cout << x + 1 << " " << y + 1 << "\n";
}
// print();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
3 2 2 0 1 3 1 3 1 2 3 0 0
output:
13 2 1 3 2 4 3 1 4 3 1 3 4 2 3 2 3 2 4 1 2 3 2 3 1 3 2
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
1 0 0 0 1 1 1
output:
3 2 1 2 1 2 1
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
2 2 1 0 2 1 0 2 1 0
output:
8 2 1 3 2 3 2 1 3 1 3 2 1 2 3 2 1
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 0 0 0 1 2 3 1 2 3 1 2 3
output:
19 2 1 2 1 2 1 3 2 3 2 3 2 4 3 4 3 4 3 1 4 2 4 3 4 1 3 1 2 3 1 3 1 2 3 2 1 2 3
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
3 1 2 3 1 2 3 0 0 0 1 2 3
output:
13 4 3 4 3 4 3 1 4 2 4 3 1 3 2 3 4 2 3 2 3 1 2 1 3 1 2
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
3 1 2 3 1 2 3 1 2 3 0 0 0
output:
10 1 4 2 4 3 4 1 3 1 2 3 1 3 1 2 3 2 1 2 3
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
6 0 0 0 1 2 3 1 2 3 1 2 3 4 5 6 4 5 6 4 5 6
output:
41 2 1 2 1 2 1 3 2 3 2 3 2 4 3 4 3 4 3 5 4 5 4 5 4 6 5 6 5 6 5 7 6 7 6 7 6 1 7 2 7 3 7 1 3 1 2 3 1 3 1 2 3 2 1 2 3 3 2 3 2 3 2 4 3 5 3 6 3 4 6 4 5 6 4 6 4 5 6 5 4 5 6
result:
ok correct
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3544kb
input:
6 0 0 0 1 5 6 1 2 6 1 2 3 4 2 3 4 5 3 4 5 6
output:
35 2 1 2 1 2 1 3 2 3 2 3 2 4 3 4 3 4 3 5 4 5 4 5 4 6 5 6 5 6 5 7 6 7 6 7 6 1 7 2 7 3 7 1 3 1 2 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1
result:
wrong answer Invalid step 26.