QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#182570 | #6414. Classical Maximization Problem | jackwas | WA | 89ms | 8836kb | C++14 | 3.6kb | 2023-09-18 08:53:23 | 2023-09-18 08:53:25 |
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);
}
}
forn(i, gy[y[p]].size()) {
int nx = gy[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();
}
sort(sx.begin(), sx.end());
sort(sy.begin(), sy.end());
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;
vector<int> ans3;
forn(i, n) if (!used[i]) ans3.pb(i + 1);
forn(i, ans3.size()) {
cout << ans3[i] sp ans3[i + 1] el;
i++;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8564kb
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 4 2 1 3 2 3 1 4 2 0 1 2 3 4
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 89ms
memory: 8836kb
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:
2 1 3 2 4 2 5 1 6 2 3 4 0 1 2 5 5 2 4 3 9 6 7 10 11 12 1 8 6 5 1 4 2 6 14 12 3 8 13 7 10 9 11 1 1 2 32 58 1 10 48 49 16 50 4 34 53 65 51 39 60 66 45 52 5 59 14 9 3 23 6 64 42 32 19 40 27 41 30 15 44 21 2 56 17 38 13 54 25 26 33 46 18 31 43 57 35 28 47 24 63 22 11 36 7 61 62 29 12 8 20 37 55 2 1 6 3 ...
result:
wrong answer wrong number of friendly pairs: printed 2, but it is actually 0 (test case 1)