QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209983#6414. Classical Maximization ProblemConfucianDonutWA 189ms11456kbC++142.5kb2023-10-10 21:04:102023-10-10 21:04:11

Judging History

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

  • [2023-10-10 21:04:11]
  • 评测
  • 测评结果:WA
  • 用时:189ms
  • 内存:11456kb
  • [2023-10-10 21:04:10]
  • 提交

answer

#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector <pair <int,int> > graph[300000];
vector <pair <int,int>> pairs;
vector <int> notpaired;

bool hv[300000];
bool hu[300000];

int n;

void makepairs(int p) {
    hv[p] = true;
    for (int i=0; i<graph[p].size(); i++) {
        if (!hv[graph[p][i].first]) {
            makepairs(graph[p][i].first);
        }
    }
    int prev = -1;
    for (int i=0; i<graph[p].size(); i++) {
        //cout << graph[p][i].second << " " << hu[graph[p][i].second] << endl;
        if (!hu[graph[p][i].second]) {
            if (prev==-1) {
                prev = graph[p][i].second;
            }else {
                pairs.push_back({prev,graph[p][i].second});
                //cout << "CREATE PAIR:" << prev << " " << graph[p][i].second << endl;
                hu[prev] = true;
                prev = -1;
                hu[graph[p][i].second] = true;
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    for (int asdf = 0; asdf<t; asdf++) {
        cin >> n;
        n = n*2;
        for (int i=0; i<n; i++) {
            graph[i].clear();
            hv[i] = false;
            hu[i] = false;
        }
        int x,y;
        pair <int,int> points[n];
        pairs.clear();
        notpaired.clear();
        map <int,int> xp;
        map <int,int> yp;
        for (int i=0; i<n; i++) {
            cin >> points[i].first >> points[i].second;
            xp[points[i].first] = 0;
            yp[points[i].second] = 0;
        }
        int c = 0;
        for (map<int,int>::iterator it=xp.begin(); it!=xp.end(); it++) {
            it->second = c;
            c++;
        }
        c = 0;
        for (map<int,int>::iterator it=yp.begin(); it!=yp.end(); it++) {
            it->second = c;
            c++;
        }
        int u,v;
        for (int i=0; i<n; i++) {
            u = xp[points[i].first];
            v = yp[points[i].second]+n;
            graph[u].push_back({v,i});
            graph[v].push_back({u,i});
        }
        makepairs(0);
        cout << pairs.size() << endl;
        for (int i=0; i<pairs.size(); i++) {
            cout << pairs[i].first+1 << " " << pairs[i].second+1 << endl;
        }
        for (int i=0; i<n; i++) {
            if (!hu[i]) {
                notpaired.push_back(i);
            }
        }
        for (int i=0; i<notpaired.size(); i++) {
            cout << notpaired[i]+1 << " " << notpaired[i+1]+1 << endl;
            i++;
        }
    }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10668kb

input:

3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3

output:

2
2 4
1 3
2
1 2
3 4
0
1 2
3 4

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 189ms
memory: 11456kb

input:

10000
2
-107276936 -310501829
419434212 585811870
-65754386 -491212232
381152038 897148193
3
-474045168 493506332
299114415 540203303
165808153 983551
-506936261 -694189769
766718170 -725540031
975267148 -593051087
1
-818952276 -762387923
584023914 -612401389
6
-77701228 -266484128
659434465 6322062...

output:

0
1 2
3 4
1
4 4
1 2
3 5
6 1
0
1 2
0
1 2
3 4
5 6
7 8
9 10
11 12
3
12 7
8 10
3 1
2 4
5 6
9 11
13 14
1
1 6
2 4
0
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
1...

result:

wrong answer pair 1 is 4=4 (test case 2)