QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#333531#5583. Color Tubesjoelgun14#WA 0ms3780kbC++144.0kb2024-02-20 06:08:212024-02-20 06:08:22

Judging History

你现在查看的是最新测评结果

  • [2024-02-20 06:08:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3780kb
  • [2024-02-20 06:08:21]
  • 提交

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();
}

詳細信息

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.