QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #500733 | #6407. Classical A+B Problem | ucup-team2307# | Compile Error | / | / | C++20 | 3.6kb | 2024-08-01 19:18:59 | 2024-08-01 19:19:00 |
Judging History
answer
```cpp
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct Points {
int n;
vector<set<array<int, 2>>> X_to_pts, Y_to_pts;
priority_queue<array<int, 2>> Xq, Yq;
Points(vector<array<int, 2>> pts) : n(pts.size()), X_to_pts(n), Y_to_pts(n) {
vector<int> X, Y;
for(auto &[x, y] : pts) {
X.push_back(x);
Y.push_back(y);
}
sort(all(X)); sort(all(Y));
for(auto &[x, y] : pts) {
x = lower_bound(all(X), x) - X.begin();
y = lower_bound(all(Y), y) - Y.begin();
X_to_pts[x].insert({x, y});
Y_to_pts[y].insert({x, y});
}
for(int i = 0; i < n; i++) {
Xq.push({X_to_pts[i].size(), i});
Yq.push({Y_to_pts[i].size(), i});
}
}
int getX() {
while(Xq.size()) {
auto [cnt, x] = Xq.top(); Xq.pop();
if(X_to_pts[x].size() == cnt) {
return x;
}
}
return -1;
}
int getY() {
while(Yq.size()) {
auto [cnt, y] = Yq.top(); Yq.pop();
if(Y_to_pts[y].size() == cnt) {
return y;
}
}
return -1;
}
void delete_point(int x, int y) {
X_to_pts[x].erase({x, y});
Y_to_pts[y].erase({x, y});
Xq.push({X_to_pts[x].size(), x});
Yq.push({Y_to_pts[y].size(), y});
}
};
vector<array<int, 4>> solve(int n, vector<array<int, 2>> pts) {
Points p(pts);
vector<array<int, 4>> ans;
auto finish = [&](auto chuj) {
int s = chuj.size();
for(int i = 0; i < s - i; i++) {
ans.push_back({chuj[i][0], chuj[i][1], chuj[s - i][0], chuj[s - i][1]});
}
};
for(int iters = 0; iters < n; iters++) {
int x = p.getX();
int y = p.getY();
vector<array<int, 2>> chuj;
if(p.X_to_pts[x].size() == 2*(n-iters)) {//everything has this x
vector<array<int, 2>> chuj;
chuj.insert(chuj.end(), all(p.X_to_pts[x]));
} else if(p.Y_to_pts[y].size() == 2*(n-iters)) {//everything has this y
chuj.insert(chuj.end(), all(p.Y_to_pts[y]));
} else if(p.X_to_pts[x].size() == 1) {//all x distinct
while(chuj.size() < 2*(n - iters)) {
int y = p.getY();
vector<array<int, 2>> tmp(all(p.Y_to_pts[y]));
chuj.insert(chuj.end(), all(tmp));
for(auto [u, v] : tmp) p.delete_point(u, v);
}
} else if(p.Y_to_pts[y].size() == 1) {//all x distinct
while(chuj.size() < 2*(n - iters)) {
int x = p.getX();
vector<array<int, 2>> tmp(all(p.X_to_pts[x]));
chuj.insert(chuj.end(), all(tmp));
for(auto [u, v] : tmp) p.delete_point(u, v);
}
}
if(chuj.size()) {
finish(chuj);
return ans;
}
auto A = *p.X_to_pts[x].begin();
if(A == array<int, 2>{x, y}) A = *p.X_to_pts[x].rbegin();
auto B = *p.Y_to_pts[y].begin();
if(B == array<int, 2>{x, y}) B = *p.Y_to_pts[y].rbegin();
ans.push_back({A[0], A[1], B[0], B[1]});
p.delete_point(A[0], A[1]);
p.delete_point(B[0], B[1]);
}
return ans;
}
main() {
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
vector<array<int, 2>> pts(2*n);
map<array<int, 2>, int> id;
int I = 0;
for(auto &[x, y] : pts) {
cin >> x >> y;
id[{x, y}] = I++;
}
auto ans = solve(n, pts);
int bad = 0;
for(auto [x, y, u, v] : ans) {
bad += x==u || y==v;
}
cout<< bad << '\n';
for(auto [x, y, u, v] : ans) {
cout << id[{x, y}] << " " << id[{u, v}] << '\n';
}
}
}/*
2 piles sum <= 2
0 0
0 1
0 2
1 1
*/
```
詳細信息
answer.code:1:1: error: stray ‘`’ in program
1 | ```cpp
| ^
answer.code:1:2: error: stray ‘`’ in program
1 | ```cpp
| ^
answer.code:1:3: error: stray ‘`’ in program
1 | ```cpp
| ^
answer.code:138:1: error: stray ‘`’ in program
138 | ```
| ^
answer.code:138:2: error: stray ‘`’ in program
138 | ```
| ^
answer.code:138:3: error: stray ‘`’ in program
138 | ```
| ^
answer.code:1:4: error: ‘cpp’ does not name a type
1 | ```cpp
| ^~~
answer.code: In constructor ‘Points::Points(std::vector<std::array<int, 2>, std::allocator<std::array<int, 2> > >)’:
answer.code:26:50: warning: narrowing conversion of ‘(&((Points*)this)->Points::X_to_pts.std::vector<std::set<std::array<int, 2> > >::operator[](((std::vector<std::set<std::array<int, 2> > >::size_type)i)))->std::set<std::array<int, 2> >::size()’ from ‘std::set<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
26 | Xq.push({X_to_pts[i].size(), i});
| ~~~~~~~~~~~~~~~~^~
answer.code:27:50: warning: narrowing conversion of ‘(&((Points*)this)->Points::Y_to_pts.std::vector<std::set<std::array<int, 2> > >::operator[](((std::vector<std::set<std::array<int, 2> > >::size_type)i)))->std::set<std::array<int, 2> >::size()’ from ‘std::set<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
27 | Yq.push({Y_to_pts[i].size(), i});
| ~~~~~~~~~~~~~~~~^~
answer.code: In member function ‘void Points::delete_point(int, int)’:
answer.code:53:42: warning: narrowing conversion of ‘(&((Points*)this)->Points::X_to_pts.std::vector<std::set<std::array<int, 2> > >::operator[](((std::vector<std::set<std::array<int, 2> > >::size_type)x)))->std::set<std::array<int, 2> >::size()’ from ‘std::set<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
53 | Xq.push({X_to_pts[x].size(), x});
| ~~~~~~~~~~~~~~~~^~
answer.code:54:42: warning: narrowing conversion of ‘(&((Points*)this)->Points::Y_to_pts.std::vector<std::set<std::array<int, 2> > >::operator[](((std::vector<std::set<std::array<int, 2> > >::size_type)y)))->std::set<std::array<int, 2> >::size()’ from ‘std::set<std::array<int, 2> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
54 | Yq.push({Y_to_pts[y].size(), y});
| ~~~~~~~~~~~~~~~~^~
answer.code: At global scope:
answer.code:107:2: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
107 | main() {
| ^~~~