QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210017#6414. Classical Maximization ProblemConfucianDonutWA 202ms11648kbC++142.9kb2023-10-10 21:51:112023-10-10 21:51:11

Judging History

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

  • [2023-10-10 21:51:11]
  • 评测
  • 测评结果:WA
  • 用时:202ms
  • 内存:11648kb
  • [2023-10-10 21:51:11]
  • 提交

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, int par) {
    hv[p] = true;
    for (int i=0; i<graph[p].size(); i++) {
        if (!hv[graph[p][i].first]) {
            makepairs(graph[p][i].first,graph[p][i].second);
        }
    }
    int prev = -1;
    //cout << p << endl;
    for (int i=0; i<graph[p].size(); i++) {
        //cout << graph[p][i].second << " " << hu[graph[p][i].second] << " " << prev << endl;
        if (graph[p][i].second == par) {
            continue;
        }
        if (!hu[graph[p][i].second]) {
            if (prev==-1) {
                prev = graph[p][i].second;
            }else {
                pairs.push_back(make_pair(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;
            }
        }
    }
    if (prev!=-1&&par!=-1) {
        hu[prev] = true;
        hu[par] = true;
        pairs.push_back(make_pair(prev,par));
    }
}

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(make_pair(v,i));
            graph[v].push_back(make_pair(u,i));
        }
        for (int i=0; i<n; i++) {
            if (!hv[i]) {
                makepairs(i,-1);
            }
        }
        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: 10608kb

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
3 1
2
1 2
3 4
0
1 2
3 4

result:

ok ok (3 test cases)

Test #2:

score: 0
Accepted
time: 202ms
memory: 11648kb

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
0
1 2
3 4
5 6
0
1 2
0
1 2
3 4
5 6
7 8
9 10
11 12
0
1 2
3 4
5 6
7 8
9 10
11 12
13 14
0
1 2
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
0
1 2
3 4...

result:

ok ok (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 187ms
memory: 10780kb

input:

10000
1
999855386 999580905
999342928 999615227
21
999601032 999015398
999155628 999176944
999309856 999524434
999121011 999509537
999323572 999685730
999272272 999769606
999450559 999390758
999632027 999178534
999024993 999463838
999784856 999374197
999980525 999366771
999241260 999516879
999599548...

output:

0
1 2
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
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
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
0
1 2
3 4
5 6
7...

result:

wrong answer worse than author's solution: expected 1, found 0 (test case 3954)