QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209983 | #6414. Classical Maximization Problem | ConfucianDonut | WA | 189ms | 11456kb | C++14 | 2.5kb | 2023-10-10 21:04:10 | 2023-10-10 21:04:11 |
Judging History
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)