QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521668#2193. Cactus RevengesocpiteWA 0ms3808kbC++232.0kb2024-08-16 13:48:252024-08-16 13:48:25

Judging History

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

  • [2024-08-16 13:48:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3808kb
  • [2024-08-16 13:48:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

int no(){
    cout << "-1";
    return 0;
}

int main() {
    set<pair<int, int>> st;
    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        st.insert({x, i});
    }

    vector<pair<int, int>> vec;

    while(!st.empty()){
        auto ele = *st.begin();
        st.erase(st.begin());
        if(ele.first == 1){
            if(st.empty())return no();
            auto it = st.lower_bound({3, 0});
            if(it == st.end())it = st.lower_bound({2, 0});
            if(it == st.end()){
                if(st.size() > 2)return no();
                vec.push_back({ele.second, st.begin()->second});
                break;
            }
            auto nw = *it;
            st.erase(it);
            nw.first--;
            vec.push_back({nw.second, ele.second});
            st.insert(nw);
        } 
        else if(ele.first == 2){
            if(st.size() < 2 || st.begin()->first != 2)return no();
            auto it = st.lower_bound({4, 0});
            if(it == st.end())it = st.lower_bound({3, 0});
            if(it == st.end()){
                if(st.size() < 2)return no();
                int prv = ele.second;
                for(auto v: st){
                    vec.push_back({prv, v.second});
                    prv = v.second;
                }
                vec.push_back({prv, ele.second});
                break;
            }
            else {
                auto nxt = *st.begin();
                st.erase(st.begin());
                vec.push_back({nxt.second, ele.second});
                vec.push_back({nxt.second, it->second});
                vec.push_back({ele.second, it->second});
                auto nw = *it;
                nw.first -= 2;
                st.erase(it);
                st.insert(nw);
            }
        }
    }
    cout << vec.size() << "\n";
    for(auto v: vec)cout << "2 " << v.first << " " << v.second << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3808kb

input:

5
2 2 3 2 1

output:

5
2 3 5
2 1 2
2 2 3
2 3 4
2 4 1

result:

ok ok, n = 5

Test #2:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

4
3 3 2 2

output:

-1

result:

ok ok, n = 4

Test #3:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

6
1 2 1 1 2 1

output:

-1

result:

ok ok, n = 6

Test #4:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

15
1 4 3 2 2 2 2 2 4 4 2 2 2 2 2

output:

18
2 3 1
2 4 3
2 4 2
2 3 2
2 5 2
2 5 9
2 2 9
2 7 6
2 7 10
2 6 10
2 8 9
2 9 10
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 8

result:

ok ok, n = 15

Test #5:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

2
1 1

output:

1
2 1 2

result:

ok ok, n = 2

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3544kb

input:

3
1 1 1

output:

1
2 1 2

result:

wrong answer incorrect degree of vertex 3: expected 1, found 0