QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#182566 | #6414. Classical Maximization Problem | jackwas | WA | 0ms | 8356kb | C++14 | 3.0kb | 2023-09-18 08:39:36 | 2023-09-18 08:39:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define el << '\n'
#define spe << ' '
#define sp spe <<
#define umap unordered_map
#define uset unordered_set
#define prqu priority_queue
#define fornr(i, j, n) for (int i = j; i < n; i++)
#define forn(i, n) for (int i = 0; i < n; i++)
#define forn1(i, n) for (int i = 1; i <= n; i++)
#define fornrb(i, j, n) for (int i = n - 1; i >= j; i--)
#define fornb(i, n) for (int i = n - 1; i >= 0; i--)
#define forn1b(i, n) for (i = n; i > 0; i--)
#define fornn(i, n) for (int i = 1; i <= n; i++)
#define rety cout << "YES\n"; return 0;
#define retn cout << "NO\n"; return 0;
#define conty cout << "YES\n"; continue;
#define contn cout << "NO\n"; continue;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
const int IMX = 2e9 + 5;
const ll LMX = 4e18 + 10, MOD = 1e9 + 7, MOD2 = 998244353;
const int MAXN = 1e5 + 5;
int x[MAXN], y[MAXN], n;
vector<int> gx[MAXN], gy[MAXN], ans1, ans2;
bool visited[MAXN], used[MAXN];
void dfs(int p, int f = MAXN - 1) {
visited[p] = 1;
forn(i, gx[x[p]].size()) {
int nx = gx[x[p]][i];
if (nx == p || nx == f) continue;
if (!visited[nx]) dfs(nx, p);
if (!used[p] && !used[nx]) {
used[p] = 1;
used[nx] = 1;
ans1.pb(p);
ans2.pb(nx);
}
}
if (!used[p] && f < n && !used[f]) {
used[f] = 1;
used[p] = 1;
ans1.pb(f);
ans2.pb(p);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> n;
n *= 2;
set<int> xv, yv;
vector<int> sx, sy;
forn(i, n) {
cin >> x[i] >> y[i];
if (xv.insert(x[i]).second) sx.pb(x[i]);
if (yv.insert(y[i]).second) sy.pb(y[i]);
visited[i] = 0;
used[i] = 0;
gx[i].clear();
gy[i].clear();
ans1.clear();
ans2.clear();
}
forn(i, n) {
int l = 0, r = sx.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (sx[m] == x[i]) {
l = m;
r = m;
} else if (sx[m] < x[i]) l = m + 1;
else r = m - 1;
}
x[i] = l;
l = 0, r = sy.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (sy[m] == y[i]) {
l = m;
r = m;
} else if (sy[m] < y[i]) l = m + 1;
else r = m - 1;
}
y[i] = l;
gx[x[i]].pb(i);
gy[y[i]].pb(i);
}
forn(i, n) {
if (!visited[i]) dfs(i);
}
cout << ans1.size() el;
forn(i, ans1.size()) cout << ans1[i] + 1 sp ans2[i] + 1 el;
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 8356kb
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 1 2 3 4 2 3 1 4 2 0
result:
wrong output format Unexpected end of file - int32 expected (test case 3)