QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#210040 | #6414. Classical Maximization Problem | ConfucianDonut | WA | 3ms | 27184kb | C++14 | 3.0kb | 2023-10-10 22:41:24 | 2023-10-10 22:41:24 |
Judging History
answer
#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector <pair <int,int> > graph[1000000];
vector <pair <int,int> > pairs;
vector <int> notpaired;
bool hv[1000000];
bool hu[1000000];
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) {
cout << "CREATE PAIR:" << prev << " " << par << endl;
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 << "ANS:" << 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: 0
Wrong Answer
time: 3ms
memory: 27184kb
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:
5 1 0 -1 3 0 1 CREATE PAIR:1 3 1 2 0 -1 3 1 -1 4 0 0 -1 2 0 -1 CREATE PAIR:2 0 0 0 1 -1 1 1 -1 2 3 ANS:2 2 4 3 1 6 2 0 -1 7 3 0 -1 0 0 0 -1 1 0 0 CREATE PAIR:0 1 2 0 -1 3 0 2 CREATE PAIR:2 3 1 2 3 ANS:2 1 2 3 4 0 0 0 -1 1 1 0 -1 2 2 0 -1 3 3 0 -1 ANS:0 1 2 3 4
result:
wrong answer Integer parameter [name=k] equals to 5, violates the range [0, 2] (test case 1)